一眼就能看出来这是一道dp题
显而易见每次操作的右端点一定是n，每株玉米被拔高的次数随位置不下降
用f(i,j) 表示以第i 株玉米结尾它被拔高了j 次的最长序列长度。
\(f(i,j)=Max(f(p,q)+1)(0<=p<i,0<=q<j,a_p+q<a_i+j\)]
复杂度是\(O(n^2k^2)\)
显然过不了这题
用d(i, j) 表示到目前为止结尾玉米被拔高了i 次高度为j的最长序列长度。
我们需要不断更新这个表(当然不会下降) ，并查询二维前缀最大值。
这珂以用二维树状数组来维护
复杂度\(O(n \log n k \log k)\)
#include <bits/stdc++.h>
#define getchar nc
#define N 10005
#define K 505
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline int Max(register int a,register int b)
{
return a>b?a:b;
}
int n,k,tr[N][K],h[N],mx,ans=0;
inline int lb(register int x)
{
return x&(-x);
}
inline int query(register int x,register int y)
{
int res=0;
for(register int i=x;i;i-=lb(i))
for(register int j=y;j;j-=lb(j))
res=Max(tr[i][j],res);
return res;
}
inline void update(register int x,register int y,register int v)
{
for(register int i=x;i<=mx+k;i+=lb(i))
for(register int j=y;j<=k+1;j+=lb(j))
tr[i][j]=Max(tr[i][j],v);
}
int main()
{
n=read(),k=read();
for(register int i=1;i<=n;++i)
{
h[i]=read();
mx=Max(mx,h[i]);
}
for(register int i=1;i<=n;++i)
for(register int j=k;j>=0;--j)
{
int x=query(h[i]+j,j+1)+1;
ans=Max(ans,x);
update(h[i]+j,j+1,x);
}
write(ans);
return 0;
}
这已经能过这题了，但我们还珂以继续优化
我们珂以发现每次树状数组查询都有大量重复计算
所以珂以变成一维树状数组
#include <bits/stdc++.h>
#define getchar nc
#define N 10005
#define K 505
#define V 5005
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline int Max(register int a,register int b)
{
return a>b?a:b;
}
int n,k,ans,h[N],f[N][K];
struct BinaryIndexTree{
int maxx[V];
inline void update(register int pos,register int v)
{
++pos;
for(register int i=pos;i<=V-1;i+=i&(-i))
maxx[i]=Max(maxx[i],v);
}
inline int query(register int pos)
{
int res=0;
++pos;
for(register int i=pos;i;i-=i&(-i))
res=Max(res,maxx[i]);
return res;
}
}tr1[K];
struct BinaryIndexTree2{
int maxx[K];
inline void update(register int pos,register int v)
{
++pos;
for(register int i=pos;i<=k+1;i+=i&(-i))
maxx[i]=Max(maxx[i],v);
}
inline int query(register int pos)
{
int res=0;
++pos;
for(register int i=pos;i;i-=i&(-i))
res=Max(res,maxx[i]);
return res;
}
}tr2[K+V];
int main()
{
n=read(),k=read();
for(register int i=1;i<=n;++i)
h[i]=read();
for(register int i=1;i<=n;++i)
for(register int j=0;j<=k;++j)
{
int tmp1=tr1[j].query(h[i]),tmp2=tr2[h[i]+j].query(j);
f[i][j]=Max(tmp1,tmp2)+1,ans=Max(ans,f[i][j]);
tr1[j].update(h[i],f[i][j]),tr2[h[i]+j].update(j,f[i][j]);
}
write(ans);
return 0;
}