DP训练——树状数组优化DP

树状数组DP

BZOJ1264
题意
给出两个长度均为 $5*n(n<=20000)$ 的数字序列，求 $LCS$ 。
数据保证每个序列中， $1$ 到 $n$ 共 $n$ 个数字每个必然出现 $5$ 次。
题解
题目说了一个数会出现 $5$ 次，那么我们可以预处理得到：第一个序列 $a[]$ 每个数字分别在哪些位置。
因为求LCS的状态转移方程中当 $s1[i-1] == s2[j-1]$ 时， $dp[i][j] = dp[i-1][j-1] + 1$
即只有当两个点相同时，值才会 $+1$ 。
于是，我们可以对第二个序列 $b[]$ 遍历一遍，对于 $b[i]$ 我们可以找到它在 $a[]$ 上的 $5$ 个位置，这 $5$ 个位置的 $dp[pos]$ 都可以被更新。
更新时用树状数组维护dp数组 $f$ 即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20000*5+5;
const int INF=0x3f3f3f3f;
int n;
int a[maxn],b[maxn];
int c[maxn];
vector<int>p[maxn/5];
int f[maxn]; //f[i]表示以a[i]结尾的与b序列的最长LCS长度
int ans=0;
void add(int x,int v){
    for(int i=x;i<=n;i+=i&-i) c[i]=max(c[i],v);
}
int query(int x){
    int res=0;
    for(int i=x;i>=1;i-=i&-i) res=max(res,c[i]);
    return res;
}
void dp(){
    for(int i=1;i<=n;i++){
        for(int j=p[b[i]].size()-1;j>=0;j--){
            int pos=p[b[i]][j];
            f[pos]=query(pos-1)+1;
//            D(pos);D(f[pos]);E;
            add(pos,f[pos]);
        }
    }
    for(int i=1;i<=n;i++) ans=max(ans,f[i]);
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ1264.in","r",stdin);
    scanf("%d",&n);
    n*=5;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        p[a[i]].push_back(i); //记录每个数字的位置
    }
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    dp();
    printf("%d",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ3594
题意
$n(n<=10000)$ 个数字排成一行，最多进行 $k(k<=500)$ 次操作。
每次可以将一个区间内所有数字 $+1$ ，或者去除任意个数字。
为使得最后的序列单调不下降，求最后剩余的数字个数的最大值。
题解
状态定义： $f[i,j]$ 表示以 $i$ 结尾，被 $j$ 个拔高区间覆盖过的最长单调不下降子序列的长度
目标： $max(f[i,j])$
边界： $f[0,0]=0$
转移方程： $f[i,j]=max(f[k,l])+1,k<i,l<=j,h[k]+l<=h[i]+j$
时间复杂度 $O(n^{2}k^{2})$
考虑优化时间复杂度。
正常的二维树状数组只可以维护 $k<i,l<=j,h[k]+l<=h[i]+j$ 中的两个条件，又注意到第一维可以用类似 $01$ 背包的思想压缩。
因此将状态第一维压缩，将 $h[k]+l<=h[i]+j$ 这个条件转化到状态定义中，再将第三维的枚举改为逆序循环（避免第一维均为 $i$ 的状态间相互转移），即可用二维树状数组维护 $f$ 数组的最值。
状态定义： $f[j,k]$ 表示以 $i$ 结尾，高度（拔高后的高度）小于等于 $j(j=h[i]+k)$ ，被 $k$ 个拔高区间覆盖过的最长单调不下降子序列的长度
目标： $max(f[j,k])$
边界： $f[,0]=0$
转移方程： $f[j,k]=max(f[y,z])+1,j<=y,z<=k$
PS：
拔高次数范围为 $[0,k]$ ，树状数组不能处理 $0$ 这个下标，所以这里将范围转化为 $[1,k+1]$ 。
因为 $f$ 数组为中间量，所以并没有在代码中显式定义。
题解链接 https://www.luogu.com.cn/problemnew/solution/P3287
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int maxa=5000+5;
const int maxk=500+5;
const int INF=0x3f3f3f3f;
int n,k;
int a[maxn];
int c[maxa+maxk][maxk];
int mx1=-INF,mx2;
int ans=-INF;
void add(int x,int y,int v){
    for(int i=x;i<=mx1;i+=i&-i) for(int j=y;j<=mx2;j+=j&-j) c[i][j]=max(c[i][j],v);
}
int ask(int x,int y){
    int res=-INF;
    for(int i=x;i>=1;i-=i&-i) for(int j=y;j>=1;j-=j&-j) res=max(res,c[i][j]);
    return res;
}
void dp(){
    /*
    f[i,j,k]表示当前这个点i是（从左往右枚举点），
    以一个高度（拔高后的高度）小于等于j(j=h[i]+k)，
    被小于等于k个拔高区间覆盖过的点为结尾的最长不下降序列的长度。
    利用类似于01背包的特性，可以去掉状态的第一维，但k的循环要变成逆序。（状态中的j可以通过i和k算出）
    c[i,j]表示以高度小于等于i，被拔高区间的覆盖次数小于等于j的点为结尾的所有不下降序列长度的最大值
    */
    for(int i=1;i<=n;i++){
        for(int j=k;j>=0;j--){
            int temp=ask(a[i]+j,j+1)+1; //j+1的原因是树状数组不能处理0这个下标，所以这一维上的下标需要向右平移一个单位
            ans=max(ans,temp);
            add(a[i]+j,j+1,temp);
        }
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("BZOJ3594.in","r",stdin);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        mx1=max(mx1,a[i]);
    } 
    mx1+=k; //最大玉米高度为max{a[i]}+k
    mx2=k+1; //拔高次数范围为[0,k]，树状数组不能处理0这个下标，所以这里将范围转化为[1,k+1]
    dp();
    printf("%d",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ2131
题意
$n(n<=1e5)$ 个馅饼，第 $i$ 个馅饼分值为 $v[i]$ 在 $t[i](t[i]<=1e8)$ 时刻，落在 $p[i]$ 位置， $p[i]$ 处于 $[1,W](W<=1e8)$ 坐标范围内。
玩家初始时刻可处于任意位置，每个时刻可以向左右移动不超过两格，求接到的馅饼分值和的最大值。
题解
首先考虑朴素dp，将馅饼按照落地时间排序。
状态定义： $f[i]$ 表示接住第 $i$ 个馅饼的最大分值
目标： $max_{1<=i<=n}f[i]$
边界： $f[0]=0$
转移方程： $f[i]=max_{j<i}(f[j])+v[i],|p[i]-p[j]|<=2*(t[i]-t[j])$
时间复杂度 $O(n^2)$
考虑优化时间复杂度。
注意到转移时需要维护满足 $|p[i]-p[j]|<=2*(t[i]-t[j])$ 的最大 $f[j]$ ，故尝试拆解该条件。
去绝对之后，该条件转换为
$-2*t[i]+2*t[j]<=p[i]-p[j]$
$p[i]-p[j]<=2*t[i]-2*t[j]$
分离参数得
$2*t[j]+p[j]<=p[i]+2*t[i]$
$2*t[j]-p[j]<=2*t[i]-p[i]$
令 $2*t[i]+p[i]=a[i],2*t[i]-p[i]=b[i]$ 得
$a[j]<=a[i],b[j]<=b[i]$
即将条件转化为维护二维前驱最大值，使用二维树状数组维护即可。
PS：为了解决二维树状数组空间过大的问题，可对 $b$ 数组进行排序后，离散化 $a$ 数组。
题解链接 https://blog.csdn.net/jaihk662/article/details/78145476
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int W,n;
struct node{
    int x,y,v;
    bool operator<(const node& h)const{return y<h.y||(y==h.y&&x<h.x);}
}pie[maxn];
int f[maxn];
int c[maxn];
int a[maxn],cnt=0;
void add(int x,int v){
    for(int i=x;i<=cnt;i+=i&-i) c[i]=max(c[i],v);
}
int ask(int x){
    int res=-INF;
    for(int i=x;i>=1;i-=i&-i) res=max(res,c[i]);
    return res;
}
void pre(){
    sort(pie+1,pie+n+1);
    sort(a+1,a+cnt+1);
    cnt=unique(a+1,a+cnt+1)-a-1;
}
void dp(){
    for(int i=1;i<=n;i++){ //循环顺序保证了y递增
        int pos=lower_bound(a+1,a+cnt+1,pie[i].x)-a; //二分查找后 得到符合条件的x下标
        f[pos]=ask(pos)+pie[i].v;
        add(pos,f[pos]);
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ2131.in","r",stdin);
    scanf("%d%d",&W,&n);
    int t,p;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&t,&p,&pie[i].v);
        pie[i].x=2*t+p;
        pie[i].y=2*t-p;
        a[++cnt]=pie[i].x;
    }
    pre();
    dp();
    printf("%d",ask(cnt)); //注意这里不是f[cnt]，因为此时的f[cnt]里存储值时没有加入最后一块馅饼的状态
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif