bzoj3594: [Scoi2014]方伯伯的玉米田

dp新优化姿势。。。

首先，当我们拔高时，一定右端点是n最优。因为如果右端点是r，相当于降低了r之后玉米的高度。显然n更优。

那么可以dp。dp[i][j]表示前i个拔高j次的LIS。dp[i][j]=max(dp[i'][j'])+1，其中h[i']+j'>=h[i],j'<=k

可以用二位树状数组来维护。

#include<bits/stdc++.h>
using namespace std;
#define N 10005
#define lowbit(x) (x&-x)
int n,k,h[N],r[N][505],H,ans;
int read(){
    int tmp=0,f=1,a=getchar();
    while(a<'0' || a>'9') {if(a=='-') f=-1; a=getchar();}
    while(a>='0' && a<='9') tmp=tmp*10+a-'0',a=getchar();
    return tmp*f;
}
void update(int x,int y,int a){
    for(int i=x;i<=H+k;i+=lowbit(i))
       for(int j=y;j<=k+1;j+=lowbit(j))
         r[i][j]=max(r[i][j],a);
}
int query(int x,int y){
    int ret=0;
    for(int i=x;i;i-=lowbit(i))
      for(int j=y;j;j-=lowbit(j))
        ret=max(ret,r[i][j]);
    return ret;
}
int main(){
    n=read(); k=read();
    for(int i=1;i<=n;i++) h[i]=read(),H=max(H,h[i]);
    for(int i=1;i<=n;i++)
      for(int j=k;j>=0;j--){
           int tmp=query(h[i]+j,j+1)+1;
           ans=max(ans,tmp);
           update(h[i]+j,j+1,tmp);
      }
    printf("%d
",ans);
    return 0;
}