bzoj3594 方伯伯的玉米田 树状数组优化dp

本文主要是介绍bzoj3594 方伯伯的玉米田 树状数组优化dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

f[i][j]表示到第i位，使用了j次机会的最长不下降子序列长度

转移：f[i][j]=max(f[x][y])+1;

x<i; y<=j; a[x]+y<=a[i]+j;

所以根据后两个条件维护二维树状数组求最值

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,k;
int a[10005],c[505][5505],f[10005][505];
int lowbit(int x){return x&(-x);}
int query(int x,int y){int ans=0;while(x){int i=y;while(i){ans=max(ans,c[x][i]);i-=lowbit(i);}x-=lowbit(x);}return ans;
}
void update(int x,int y,int z){while(x<=k+1){int i=y;while(i<=m){c[x][i]=max(c[x][i],z);i+=lowbit(i);}x+=lowbit(x);}
}
int main()
{//freopen("data.in","r",stdin);//freopen("data.out","w",stdout);scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);m=max(m,a[i]);}//printf("666\n");m+=k;  int ans=0;for(int i=1;i<=n;i++){for(int j=0;j<=k;j++){f[i][j]=query(j+1,a[i]+j)+1;ans=max(ans,f[i][j]);}for(int j=0;j<=k;j++)update(j+1,a[i]+j,f[i][j]);}printf("%d\n",ans);return 0;
}

这篇关于bzoj3594 方伯伯的玉米田 树状数组优化dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---