P3287 [SCOI2014] 方伯伯的玉米田

P3287 [SCOI2014] 方伯伯的玉米田

感觉其实也不难。

我们必然知道选择加区间的右端点是 \(n\)，因为如果只选中间的话会与后面相差开，不如直接选上右，因为有两个变量，位置与操作次数，所有我们就设状态为 \(f_{x,k}\) 为我们 \(x\) 为左端点被加 \(k\) 次的最长不下降子序列，此时我们的树状数组也要开两维同样记录，查找时也两维查找。

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1 
#define re register 
const int N=1e4+10;
const int mod=1e9+7;
using namespace std;
int n,k;
int a[N];
int f[N][505];
int t[N][505];

int lb(int x){
	return x&-x;
}
void change(int x,int y,int z){
	for(int i=x;i<=5500;i+=lb(i)){
		for(int j=y;j<=k+1;j+=lb(j)){
			t[i][j]=max(t[i][j],z);
		}
	}
}
int query(int x,int y){
	int ans=0;
	for(int i=x;i;i-=lb(i)){
		for(int j=y;j;j-=lb(j)){
			ans=max(ans,t[i][j]);
		}
	}
	return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	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--){
			f[i][j]=query(a[i]+j,j+1)+1;
			change(a[i]+j,j+1,f[i][j]);
		} 
	}
	cout<<query(5500,k+1);
	return 0; 
}