[SCOI2014] 方伯伯的玉米田 题解

对于每次修改的区间以及其左边序列和右边序列，共三种情况：

• 1.区间内比两侧低的还是低
• 2.区间内比两侧低的变得比两侧高了
• 3.区间内比两侧高的还是高

那么现在又面临一个问题：在区间内变化后，对答案，即最长不下降子序列有什么影响。
对区间左边：可能会使其最长不下降子序列增长
对区间右边：可能会使其最长不下降子序列减少
综上所述：我们出正解一定要保证修改的区间右侧没有数，也就是修改区间的最后一位在 $n$ 上
然后来到最使我头疼的地方， DP 转移方程，这个简单的方程我想了好久（似乎也不是很简单）。

f[i][j] 表示以 i 结尾，被拔高了 j 次的区间之后，最长不下降子序列的长度

f[i][j]=max{f[k][l]+1(1≤k<i,0≤l≤j,h[i]+j>h[k]+l)}

然后我们用二维树状数组维护一下就好了

#include<bits/stdc++.h>
using namespace std;
#define lb(x)  (x)&(-x)
int a[10010],dp[10010][510],t[510][5510],n,k;
void update(int x,int y,int d){
	for(int i=x;i<=k+1;i+=lb(i)){
		for(int j=y;j<=5500;j+=lb(j)){
			t[i][j]=max(t[i][j],d);
		}
	}
} 
int query(int x,int y){
	int ans=0;
	for(int i=x;i>0;i-=lb(i)){
		for(int j=y;j>0;j-=lb(j)){
			ans=max(ans,t[i][j]);
		}
	}
	return ans;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=k;j>=0;j--){
			dp[i][j]=query(j+1,a[i]+j)+1;
			update(j+1,a[i]+j,dp[i][j]);
		}
	}
	cout<<query(k+1,5500);
	return 0;
}