传送门


题意:给一个数组,要你找到三元上升子序列,三元上升子序列的定义是对任意\( i \le j \le k \)有\( a_i \le a_j \le a_k \),数据规模\( 1 \leq n \leq 30000 \),\( 1 \leq a_i \leq 10^{18} \)


解答:范围太大需要离散化,离散化后\( dp[i][j] \)表示k=j的位置的i元上升子序列有多少个,使用树状数组维护前面i-1元上升子序列个数即可

状态转移方程:\( dp[i][j] = \Sigma_{x=1}^{i-1} dp[x][j-1](a[x]<a[i]) \)


 

分类: DP

0 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注