偏序关系与dp BZOJ3594（二维树状数组）

た入场券 2022-05-15 01:12 191阅读 0赞

[传送门][Link 1]

[偏序关系][Link 2]

[二维树状数组][Link 3]

这个题用dp\[i\]\[j\]表示前i个数，以h\[i\]结尾，用了j次修改，最长的非递减序列。

但是这样直接dp的话如下

for(int i=1; i<=n; i++){
            for(int j=0; j<=K; j++){
                for(int a=0; a<i; a++){
                    for(int b=0; b<=j; b++){
                        if(h[i]+j-b>=h[a])
                            dp[i][j]=max(dp[i][j], dp[a][b]+1);
                    }
                }
            }
        }

会超时。这个题巧妙的利用偏序关系，用二维树状数组将时间优化到n\*k\*logn\*logk。

如果可以转移的话必须要满足h\[i\]+j-b>=h\[a\]的条件，也就是h\[i\]+j>=h\[a\]+b，前提是i>a,j>=b，这就有三个不等式，我们i是从前往后遍历所以i>a不予考虑，剩下两个我们可以组成一个二维矩阵，用二维树状数组维护dp最大值。

内循环j要从大到小，因为i>a。注意j的取值全部+1，防止树状数组更新0值。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e4+10;
    const int M=5e2+10;
    int n, K;
    int dp[N][M];
    int s[N][M];
    int h[N];
    
    void upd(int x, int y, int v){
        for(;x<N;x+=x&-x)
            for(int t=y; t<M; t+=t&-t)
                s[x][t]=max(s[x][t], v);
    }
    
    int sum(int x, int y){
        int ret=-1;
        for(;x>0; x-=x&-x)
            for(int t=y; t>0; t-=t&-t)
                ret=max(s[x][t], ret);
        return ret;
    }
    
    int main(){
        scanf("%d%d", &n, &K);
    
        for(int i=1; i<=n; i++)
            scanf("%d", h+i);
    
        int ans=0;
        for(int i=1; i<=n; i++){
            for(int j=K+1; j>=1; j--){
                dp[i][j]=sum(h[i]+j, j)+1;
                ans=max(ans, dp[i][j]);
                upd(h[i]+j, j, dp[i][j]);
            }
        }
    
        printf("%d\n", ans);
    
        return 0;
    }

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=3594
[Link 2]: https://blog.csdn.net/du_lun/article/details/81949899
[Link 3]: http://www.cnblogs.com/RabbitHu/p/BIT.html