P3287 [SCOI2014]方伯伯的玉米田

首先可以证明，一定存在一种最优解，每次选择的区间结尾都是 \(n\)。因为如果某一个区间结尾不是 \(n\)，将其替换成 \(n\) 仍然保持单调不下降。接着都按这个策略拔高玉米。

令 \(f_{i,j}\) 表示 \(1\sim i\) 这段前缀进行了 \(j\) 次操作，第 \(\boldsymbol{i}\) 株玉米不被拔掉，所能剩下最多的玉米。

\[f_{i,j}=\max\left\{f_{p,q}\left|\right.p<i,q\leq j,a_p+q\leq a_i+j\right\}+1
\]

枚举 \(i\)，剩下两个限制用二维树状数组维护即可。

有一个小细节，操作次数可能为 \(0\)，扔进树状数组时需要加 \(1\)。

时间复杂度 \(O(nk\log k\log a)\)。

code:

#include<bits/stdc++.h>

using namespace std;

#define Max(x,y)((x)>(y)?x:y)

#define For(i,x,y)for(i=x;i<=(y);i++)

#define Down(i,x,y)for(i=x;i>=(y);i--)

#define lowbit(x)((x)&-(x))

int c[505][5505],a[10005],k,mx;

int sum(int x,int tmp)

{

	int y,res=0;

	while(x)

	{

		y=tmp;

		while(y)res=Max(c[x][y],res),y-=lowbit(y);

		x-=lowbit(x);

	}

	return res;

}

void add(int x,int tmp,int z)

{

	int y;

	while(x<=k+1)

	{

		y=tmp;

		while(y<=mx+k)c[x][y]=Max(c[x][y],z),y+=lowbit(y);

		x+=lowbit(x);

	}

}

int main()

{

	int n,i,j,tot,ans=0;

	scanf("%d%d",&n,&k);

	For(i,1,n)scanf("%d",&a[i]),mx=Max(mx,a[i]);

	For(i,1,n)

	Down(j,k,0)

	{

		tot=sum(j+1,a[i]+j)+1;

		add(j+1,a[i]+j,tot);

		ans=Max(ans,tot);

	}

	printf("%d",ans);

	return 0;

}

巴特西

P3287 [SCOI2014]方伯伯的玉米田

最新文章

热门文章