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

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

动态规划·二维树状数组

题解：

感觉自己Dp好弱啊，啥也想不出来。。。

QwQ。

有一个结论，提升[l,r]可以用提升[l,n]来替代，总不会更坏。
（像这种区间长度没有限制*度很高比较棘手的一般就是找个最优性结论限制住）

设f[i][j]表示前i个提升j次的最长LIS长度。
f[i][j]=maxf[k][l]（k<i,l≤j,ak+l≤ai+j）
三位偏序用二维树状数组维护。。。

为了避免树状数组下标有0我把下标都加了1.

Code：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int n,K,a[10005];

struct BIT{
int c[6005][605];
inline int lowbit(int x){ return x&(-x); }
void add(int x,int y,int d){
for(int i=x;i<=6000;i+=lowbit(i)){
for(int j=y;j<=600;j+=lowbit(j)){
                c[i][j]=max(c[i][j],d);
            }
        }
    }
int qmx(int x,int y){
int ans=0;
for(int i=x;i;i-=lowbit(i)){
for(int j=y;j;j-=lowbit(j)){
                ans=max(ans,c[i][j]);
            }
        }
return ans;
    }
} bit;

int main(){
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++) scanf("%d",a+i);
int ans=0, tp;
for(int i=1;i<=n;i++){
for(int j=K;j>=0;j--){
            tp=bit.qmx(a[i]+j+1,j+1)+1;
            ans=max(ans,tp);
            bit.add(a[i]+j+1,j+1,tp);
        }
    }
printf("%d\n",ans);
}