bzoj 3594 [Scoi2014]方伯伯的玉米田（DP+二维BIT）

【题目链接】

http://www.lydsy.com/JudgeOnline/problem.php?id=3594

【题意】

给定一个n个数的序列，有K次将一个区间内的数加1的机会，问最长不下降子序列。

【思路】

首先知道每次加1一个区间为[i,n]肯定不会差。

设f[i][j]为前i个数，还有j次机会的LIS，则有转移式：

f[i][j] = max{ f[a][b],h[a]+b<=h[i]+j }

则可以用二维BIT加速方程转移。

【代码】

 #include<set>

 #include<cmath>

 #include<queue>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt)

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std;

 typedef long long ll;

 const int M = +;

 const int N = +;

 ll read() {

     char c=getchar();

     ll f=,x=;

     while(!isdigit(c)) {

         if(c=='-') f=-; c=getchar();

     }

     while(isdigit(c))

         x=x*+c-'',c=getchar();

     return x*f;

 }

 int C[N][M],n,K,a[];

 int lowbit(int x)

 {

     return x&-x;

 }

 void upd(int x,int y,int v)

 {

     for(int i=x;i<N;i+=lowbit(i))

         for(int j=y;j<M;j+=lowbit(j))

             C[i][j]=max(C[i][j],v);

 }

 int query(int x,int y)

 {

     int ans=;

     for(int i=x;i;i-=lowbit(i))

         for(int j=y;j;j-=lowbit(j))

             ans=max(ans,C[i][j]);

     return ans;

 }

 int main()

 {

     n=read(),K=read();

     FOR(i,,n) a[i]=read();

     K++;

     int ans=;

     FOR(i,,n) for(int j=K;j;j--)

     {

         int x=query(j,a[i]+j)+;

         ans=max(ans,x);

         upd(j,a[i]+j,x);

     }

     printf("%d\n",ans);

     return ;

 }