自动搬运

查看原文

来自洛谷，原作者为

	gzw2005 可是这一切的平静、舒适和满足都要恐怖地结束，那可怎么办呢？

搬运于2025-08-24 21:45:12，当前版本为作者最后更新于2019-11-28 13:58:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目链接戳这里

简明题意

$Betty$ 在一条直线的 $N(1\leq N\leq 1000)$ 个目标点上跳跃，目标点i在目标点 $x(i)$，得分为 $p(i)$。$Betty$ 可选择任意一个目标点上，只朝一个方向跳跃，且每次跳跃距离成不下降序列。每跳到一个目标点，$Betty$ 可以拿到该点的得分，求最大总得分。

首先第一步当然是把这些点按照坐标从小到大排序啦。

会MLE的DP做法

定义 $f(i,j)$ 表示当前 $Betty$ 跳到了第 $i$ 个点，且最小跳跃距离为 $j$ 的最大总得分。很容易得到状态转移方程：

显然又会 MLE 又会 TLE。

正常 DP 做法

由于 $Betty$ 只朝一个方向跳跃，所以要分两种情况：一种是一直向右跳，一种是一直向左跳。

当一直向右跳时，定义 $f(i,j)$ 表示当前 $Betty$ 已经跳到了第 $i$ 个点，且最后一步是从第 $j$ 个点跳到第 $i$ 个点的最大总得分。那么

其中 $k<j<i$，$x(j)-x(k)\leq x(i)-x(j)$。

考虑边界 $f(i,i)=s(i)$。（即一开始站在任意一个点上）

当一直向左跳时也同理，只不过方向倒过来而已。只要做两次 DP 就可以了。

这个时候时间复杂度为 $O(N^3)$，由于数据水，期望 $81pts$。

优化

第一步显然：$f(i,j)=\max\{f(j,k)+s(i)\}=\max\{f(j,k)\}+s(i)$

第二步：我们观察式子：

我们发现和原来的式子非常像，好像可以直接 $f(i,j)=f(i-1,j)-s(i-1)+s(i)$，但是上面的式子定义范围会变成了$x(j)-x(k)\leq x(i-1)-x(j)$。由于 $x(i-1)<x(i)$，所以满足条件的 $k$ 会变多！所以我们需要将拓展到的 $k$ 先取一个最大值，然后才能直接转移。

因为这个时候我们是从 $i-1$ 转移到 $i$ 的，所以我们要先枚举 $j$，再枚举 $i$。

for(int j=1;j<=N;j++){
	f[j][j]=s(j);//边界
	for(int i=j+1,now=j+1;i<=N;i++){
		f[i][j]=f[i-1][j]-s(i-1);//先得到之前的max
		while(now>1 && x(j)-x(now-1)<=x(i)-x(j))
			f[i][j]=max(f[i][j],f[j][--now]);//取拓展到k的最大值
		f[i][j]+=s(i);//直接转移
		Ans=max(Ans,f[i][j]);
	}
}

如果是一直往左跳，就反着做一遍 DP 就可以了。

由于每个$k$ 只会被拓展 $1$ 次，时间复杂度为 $O(N^2)$。

程序

#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
	char ch=getchar();int f=1,num=0;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){num=num*10+ch-'0';ch=getchar();}
	return num*f;
}
int N,f[1002][1002],Ans;
struct Point{int x,s;} point[1002];
bool cmp(Point a,Point b){return a.x<b.x;}
#define x(i) point[i].x
#define s(i) point[i].s
int main(){
	N=read();
	for(int i=1;i<=N;i++)x(i)=read(),s(i)=read();
	sort(point+1,point+1+N,cmp);
	for(int j=1;j<=N;j++){
		f[j][j]=s(j);//边界
		for(int i=j+1,now=j+1;i<=N;i++){
			f[i][j]=f[i-1][j]-s(i-1);//先得到之前的max
			while(now>1 && x(j)-x(now-1)<=x(i)-x(j))
				f[i][j]=max(f[i][j],f[j][--now]);//取拓展到k的最大值
			f[i][j]+=s(i);//直接转移
			Ans=max(Ans,f[i][j]);
		}
	}
	for(int j=N;j>=1;j--){
		f[j][j]=s(j);
		for(int i=j-1,now=j-1;i>=1;i--){
			f[i][j]=f[i+1][j]-s(i+1);
			while(now<N && x(now+1)-x(j)<=x(j)-x(i))
				f[i][j]=max(f[i][j],f[j][++now]);
			f[i][j]+=s(i);
			Ans=max(Ans,f[i][j]);
		}
	}
	printf("%d",Ans);
	return 0;
}