Description

Input

Output

Sample Input

Sample Output

HINT

这题的dp状态很容易想到dp[i][j]表示前i棵玉米用了j次加+1最多留下几棵

不过转移还是挺难想的

dp[i][j]=max(dp[k][x])+1（k<i x<=j a[k]+l<=a[i]+j）

为什么是a[k]+l<=a[i]+j？

可以这么想，对于每次加其实都可以加到尾，这种加法是不会劣于只加中间一段的

因为要求不降，所以如果你只加中间一段，会导致后面一段的数和前面的数的差变大，从而可能导致使用更多的加操作。

推出式子以后，我们发现这是n*n*k*k的显然炸了。

不过他要求max，显然就想到了用数据结构维护，那当然使用最短的树状数组了。

因为有三个限制（k<i x<=j a[k]+l<=a[i]+j），难道要用三维树状数组？log^3！magic！

显然因为当算到i的时候，只有1-（i-1）会对答案产生影响，所以我们就可以像类似完全背包一样去掉一维，然后将j倒着扫一遍。这样就变成了二维树状数组了。

如果还是正着扫 那dp[i][j]有可能就从dp[i][j-1]转移 显然是不对的啦。

附上代码：

#include <cstdio>
#include <algorithm>
using namespace std; 
int a[10010],g[510][6000],n,K,ans;
int query(int x,int y)
{
	int t = 0;
	for (;x;x -= x&-x)
		for (int j = y;j;j -= j&-j)
			if (g[x][j]>t) t = g[x][j];
	return t;
}
void update(int x,int y,int d)
{
	for (;x<=K+1;x+=x&-x)
		for (int j = y;j<=5600;j+=j&-j)
			if (d>g[x][j]) g[x][j] = d;
}
 
int main()
{
	scanf("%d%d",&n,&K);
	for (int i = 1;i <= n;i++)
		scanf("%d",&a[i]);
	for (int i = 1;i <= n;i++)
		for (int j = K;j >= 0;j--)
		{
			int tmp = query(j+1,a[i]+j);
			if (ans < tmp+1) ans = tmp+1;
			update(j+1,a[i]+j,tmp+1);
		}
	printf("%d",ans);
	return 0;
}

dp的水平还是不够，zjoiday1T3根本没想到是dp，唉还是太年轻