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;
}
上一篇:HDU 1934 树状数组 也可以用线段树


下一篇:[Javascript] Advanced Console Log Arguments