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

题目链接

题目大意：给定数列，两种操作:1.区间+1(最多k次)2.删除一个数 求能够得到的最长不下降序列长度

题解：结论：每次操作区间右端点一定为n，这样保证了最优

dp[i][j]表示前i棵，操作了j次的lis长度
dp[i][j]=max(dp[k][l])+1,k<i,l<=j,a[k]+l<=a[i]+j

这是一个三维偏序，第一维i为编号天然有序，现在需要维护(j,a[i]+j)这两维，
但上面的值不是定值，没法用CDQ分治，空间足够，于是二维树状数组维护

树状数组下标不能为0，但是l和j可以为0，强制+1处理。

最后，类似1264，j需要倒序枚举，如果从小到大枚举j，后来的j可能会使用之前的j转移，逆序避免了同层状态干扰转移

我的收获：处理下标，倒着枚举处理

#include <cstdio> 
#include <cstring> 
#include <cstdlib> 
#include <cmath> 
#include <iostream> 
#include <algorithm> 

using namespace std;  

const int M=10010;

int n,m,ans,mx;
int c[6010][510];  
int dp[M][510];  
int a[M];    

void modify(int x,int y,int v)  
{  
for(int i=x;i<=mx+m;i+=i&(-i))  
for(int j=y;j<=m+1;j+=j&(-j))  
            c[i][j]=max(c[i][j],v);  
}  

int query(int x,int y)  
{  
int ret=0;  
for(int i=x;i>0;i-=i&(-i))  
for(int j=y;j>0;j-=j&(-j))  
            ret=max(ret,c[i][j]);  
return ret;
}  

void work()
{
for(int i=1;i<=n;i++)  
for(int j=m;j>=0;j--)  
        {  
            dp[i][j]=query(a[i]+j,j+1)+1;  
            ans=max(ans,dp[i][j]);  
            modify(a[i]+j,j+1,dp[i][j]);  
        }  
printf("%d\n",ans);  
}

void init()
{
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),mx=max(mx,a[i]); 
}

int main()  
{  
    init();
    work();
return 0;  
}