首页 > 代码库 > BZOJ 3594 [Scoi2014]方伯伯的玉米田（二维树状数组）
BZOJ 3594 [Scoi2014]方伯伯的玉米田（二维树状数组）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3594
【题目大意】
给出一个数列，选出k个区间使得区间内数全部加1，
求k次操作之后最长的不下降子序列
【题解】
我们发现，每次的区间右端点一定贪心选到最右端才是最优的，
那么在用树状数组统计的时候，只要一个点被+1了，那么后面的点起码+1，
我们在树状数组后面加一维统计被区间包含的次数，发现也是前缀和关系，
所以用二维树状数组统计答案即可。
为避免自身被重复统计，第二维循环降序。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=10010,M=6000,K=600;namespace Td_BIT{ int c[M][K]; void Initialize(){memset(c,0,sizeof(c));} void update(int x,int y,int val){ for(int i=x;i<M;i+=i&-i) for(int j=y;j<K;j+=j&-j)c[i][j]=max(val,c[i][j]); } int query(int x,int y){ int res=0; for(int i=x;i;i-=i&-i) for(int j=y;j;j-=j&-j)res=max(res,c[i][j]); return res; }}int n,k,a[N];int main(){ using namespace Td_BIT; Initialize(); int ans=0; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)for(int j=k;~j;j--){ int p=query(a[i]+j,j+1)+1; ans=max(ans,p); update(a[i]+j,j+1,p); }printf("%d\n",ans); return 0;}BZOJ 3594 [Scoi2014]方伯伯的玉米田（二维树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。