题意
有$n$个数,可以进行$k$次操作,每次操作可以选择一个区间让每个数$+1$,求最后最长不下降子序列长度
数据范围:$1 \le n \le 10000,1\le k \le 500$
题解
首先明确一个事实:每次操作的区间的右端点一定是$n$
容易证明:这样不会使答案变小,并且如果不这样可能会使答案变小
用$f[i][j]$表示第$i$个数已经被操作了$j$次,当前的答案,状态转移方程为$$f[i][j]=\max f[k][l]+1 \ (k<i,l \le j,S_k+l \le S_i+j)$$
可以用二维树状数组来维护$(j,S_i+j)$
并且可以将$f$降至$1$维,即用$f[i]$表示前$i$个数的答案,这是因为树状数组已经维护了$j$的信息
而在进行$dp$的时候,注意枚举$j$的时候应倒序枚举,原因类似于$01$背包,“被操作了$j$次”最多只会发生一次
因为$j$可以为$0$,所以整个数组向后推一个
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10000+10;
const int K=500+10;
const int A=5000+10;
int n,m;
int a[N];
int ans,mx;
int T[K][A+K];
inline int lowbit(int x){
return x&-x;
}
inline void update(int x,int y,int k){
for(;x<=m+1;x+=lowbit(x))
for(int i=y;i<=m+mx;i+=lowbit(i))
T[x][i]=max(T[x][i],k);
}
inline int query(int x,int y){
int res=0;
for(;x;x-=lowbit(x))
for(int i=y;i;i-=lowbit(i))
res=max(res,T[x][i]);
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
mx=max(mx,a[i]);
}
for(int i=1;i<=n;i++)
for(int j=m;~j;j--){
int t=query(j+1,j+a[i])+1;
ans=max(ans,t);
update(j+1,j+a[i],t);
}
printf("%d",ans);
return 0;
}