https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338
https://class.51nod.com/Html/Textbook/Problem.html#problemId=3928&textbookChapterId=725
保证右端点为 \(n\) 是因为如果不是这样操作,可能导致后面的数大小关系发生变化,而如果保证了,那么后面的数都增加了,不需要考虑大小关系的变化,只需要考虑变化的交界处即可。上面的代码是删去 \([a+1,i-1]\)。
注意写代码的时候更新完答案不能立刻塞入二维树状数组,因为这道题要满足三维偏序:\(a<i,b\le j,a_a+b\le a_i+j\),其实一维已经被我们的枚举顺序搞掉了。
#include<iostream>
using namespace std;
const int N=10010,K=510,AK=5510;
int n,k,a[N],f[N][K],ak;
int c[K][AK];
void add(int x,int y,int v){
for(;x<=k+1;x+=x&-x)
for(int i=y;i<=ak;i+=i&-i)
c[x][i]=max(c[x][i],v);
}
int sum(int x,int y){
int res=0;
for(;x;x-=x&-x)
for(int i=y;i;i-=i&-i)
res=max(res,c[x][i]);
return res;
}
int main(){
#ifdef LOCAL
freopen("1.txt","r",stdin);
#endif
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
cin>>n>>k;
for(int i=1;i<=n;++i)
cin>>a[i],ak=max(ak,a[i]);
ak+=k;
int ans=0;
for(int i=1;i<=n;++i){
for(int j=0;j<=k;++j){
f[i][j]=sum(j+1,a[i]+j)+1;
ans=max(ans,f[i][j]);
}
for(int j=0;j<=k;++j)add(j+1,a[i]+j,f[i][j]);
}
cout<<ans;
return 0;
}
标签:51nod,3928,玉米田,int,Html,https,ak
From: https://www.cnblogs.com/wscqwq/p/18327988