自动搬运

查看原文

来自洛谷，原作者为

	dashabi35 有痣不在年糕

搬运于2025-08-24 23:10:17，当前版本为作者最后更新于2025-04-01 22:11:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目传送门

Thinking

这道题显然是一道 dp 题。原因：当前的值和前面的有关联且无后效性（废话）。

那么 $dp[i]$ 就可以通过另一个更小的下标 $j$ 来判定。

如下：

条件：$j$ 初始为 $i$ 只到 $j<1$ 或 $i-j+1>m$ 此时结束。

$$dp[i]=\min(dp[i],dp[j-1]+k+(mmax-mmin)\times(i-j+1)) $$

$mmax$ 为 $i$ 到 $j$ 中的最大值，$mmin$ 为 $i$ 到 $j$ 中的最小值，可用两个变量 $mmax$ 和 $mmin$ 每次进行遍历（便利是顺便的，不会太占用时间复杂度）。

$i-j+1$ 即为当前的数量。

Code

这是我的第一篇题解，我希望它更加完美，经过优化，可以达到 27ms（看电脑配置）。

#include<stdio.h> //比用万能头快 
using namespace std;
long long n,m,k;
long long a[20005],dp[20005];
int main()
{
	scanf("%lld%lld%lld",&n,&m,&k); //比 cin 快 
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
	{
		long long biggest=a[i];
		long long smallest=a[i]; 
		dp[i]=2e14;
		for(int j=i;j>=1&&i-j+1<=m;j--)
		{
			if(biggest<a[j]) biggest=a[j]; //比直接调 max 快很多 
			if(smallest>a[j]) smallest=a[j]; //比直接调 min 快很多 
			long long addition=k+(i-j+1)*(biggest-smallest);
			if(dp[j-1]+addition<dp[i]) dp[i]=dp[j-1]+addition; //状态转移 
		}
	}
	printf("%lld",dp[n]); //比 cout 快 
	return 0;
}

AC记录 28ms