自动搬运

查看原文

来自洛谷，原作者为

	LlLlCc 背井离乡，忍辱负重

搬运于2025-08-24 21:44:38，当前版本为作者最后更新于2020-01-18 11:23:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：

给定n个点，坐标为1~m之间的正整数且互不相同，现在要求用一段或多段线段将n个点覆盖，每种长度的线段都有一个价格（不满足单调性），求出最小价格

看完题目第一想法就应该是DP，贪心应该是不行的

• 定义 $f$ 数组：

这题的定义还是很容易想到的，$f[i]$表示将前$i$个的覆盖所需要的最小价值，而答案就是$f[n]$了

• 转移方程：

易得：$f[i]$ $=$ $f[j-1]$ $+$ $cost[a[i]-a[j]+1]$

其中$a[i]$表示第$i$个点的位置，$cost[i]$表示长度为$i$的线段的价格

但题目明确指出，长度增加价格未必会增加，也就是说有可能更长的线段的价格反而比长度为$a[i]-a[j]+1$的便宜

因为只要长度比$a[i]-a[j]+1$更长就能覆盖，所以我们只要在$cost[a[i]-a[j]+1]$ ~ $cost[m]$选一个最小值即可，最小值怎么找？每次都$O(n)$找一遍？显然会超时，一个很简单最小后缀值提前预处理一遍就行了

详见代码：

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,m,f[maxn],Ans,lst[maxn],a[maxn],v[maxn];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
	while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int main(){
	n=read(),m=read();memset(f,63,sizeof f);f[0]=0;
	for (int i=1;i<=n;i++) a[i]=read();sort(a+1,a+n+1);
	for (int i=1;i<=m;i++) v[i]=read();v[0]=1<<30;lst[m+1]=1<<30;
	for (int i=m;i>=0;i--) lst[i]=min(v[i],lst[i+1]);
	for (int i=1;i<=n;i++)
		for (int j=i;j;j--) f[i]=min(f[i],f[j-1]+lst[a[i]-a[j]+1]);
	printf("%d",f[n]);
	return 0;
}