自动搬运

查看原文

来自洛谷，原作者为

	NS·YJD **

搬运于2025-08-24 21:47:20，当前版本为作者最后更新于2018-02-06 10:23:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先本题需要确定一个事实：

每一次的拔高操作区间右端点一定是最右边的玉米

证明：

首先无论操作区间在哪里，如果区间两边存在玉米，那么这些玉米与区间内玉米拔高后的相对高度关系只有3种情况：1.原本区间内比它们高的玉米还是比它们高。2.原本区间内比它们矮的玉米不再比它们矮。3.原本区间内比它们矮的玉米还是比它们矮。

对于区间左边而言：

这三种情况都不会减少初始排列中已存在的最长不下降序列的长度，并且有可能使它增长

对于区间右边而言：

这三种情况都不会增加初始排列中已存在的最长不下降序列的长度，并且有可能使它减少

如此一来我们就可以发现，要想得到最长不下降序列，区间的右边不存在玉米的情况一定是最优解

接下来考虑转移方程：

对于排列中的某一点，它可能已经被j个拔高区间覆盖过（0<=j<=k）。那么我们考虑在包含了这一个已经被j个拔高区间覆盖过的点的最长不下降序列中，该点左边的所有点在原排列中一定在它的左边且被j'个拔高区间覆盖过（0<=j'<=），同时被拔高后的高度不大于它。

所以得出转移方程：

ｆ［ｉ］［ｊ］表示以ｉ结尾，ｉ这个点已经被j个拔高区间覆盖过，所能得到的最长不下降序列长度。

ｆ［ｉ］［ｊ］＝ｍａｘ｛ｆ［ｋ］［ｌ］｝＋１（１＜＝ｋ＜ｉ，０＜＝ｌ＜＝ｊ，ｈ［ｉ］＋ｊ＞＝ｈ［ｋ］＋ｌ）

很明显这里是需要快速求出一个二维的前缀最大值，所以引入二位树状数组：

ｔｒｅｅ［ｉ］［ｊ］维护的是以高度（拔高后的高度）在（ｉ－ｌｏｗｂｉｔ（ｉ）＋１，ｉ），被（ｊ－ｌｏｗｂｉｔ（ｊ）＋１，ｊ）个拔高区间覆盖过的点为结尾的所有不下降序列长度的最大值

本题最难理解的地方就是这里，我写到这里的时候也有点晕

我们先再看一遍转移方程

ｆ［ｉ］［ｊ］＝ｍａｘ｛ｆ［ｋ］［ｌ］｝＋１（１＜＝ｋ＜ｉ，０＜＝ｌ＜＝ｊ，ｈ［ｉ］＋ｊ＞＝ｈ［ｋ］＋ｌ）

这里好像可以降维

利用从左往右枚举来去掉第一维后，感觉上可以用ｆ［ｉ］来表示以当前这个点之前的所有被不超过ｉ个拔高区间覆盖过的点为结尾的最长不下降序列长度，似乎这样也可以正确表示出来。

理想很丰满，现实很果敢

ｈ［ｉ］＋ｊ＞＝ｈ［ｋ］＋ｌ

这个条件意味着我们还得增加一个高度的判定

确保找到的最长不下降子序列的最后一个点拔高后的高度不会超过当前这个点拔高后的高度，而仅仅使用一维我们无法进行高度的判定，所以这里必须增加一维来进行高度的判定，这一维表示的正是高度

于是有：

ｆ［ｊ］［ｋ］表示当前这个点ｉ前面（从左往右枚举点），以一个高度（拔高后的高度）不超过ｊ（ｊ＝ｈ［ｉ］＋ｋ），被不超过ｋ个拔高区间覆盖过的点为结尾的最长不下降序列的长度

到这里我们再去看前面的二维树状数组就可以很轻松地理解了

增加一点说明：

for(int i=1;i<=n;i++）
    for(int j=k;j>=0;j--)

第二重循环的顺序必须由K递减，与背包问题同理

附上代码：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 10000+10
#define maxk 500+10
#define large 6000
using namespace std;
int n,k,mx,ans;
int h[maxn],tree[large][maxk];
int lowbit(const int a)
{
	return a&(-a);
}
void update(int pos,const int val,int sel)
{
	for(;pos<=mx+k;pos+=lowbit(pos))
	    for(int i=sel;i<=k+1;i+=lowbit(i))
		tree[pos][i]=max(tree[pos][i],val);
}
int search(int pos,int sel)
{
	int ans=0;
	for(;pos;pos-=lowbit(pos))
	    for(int i=sel;i;i-=lowbit(i))
		ans=max(ans,tree[pos][i]);
	return ans;
}
int main(void)
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&h[i]);
		mx=max(mx,h[i]);
	}
	for(int i=1;i<=n;i++)
	    for(int j=k;j>=0;j--)
	    {
	    	int x=search(h[i]+j,j+1)+1; 
	    	ans=max(ans,x);
	    	update(h[i]+j,x,j+1);
	    }
	cout<<ans<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}