自动搬运

查看原文

来自洛谷，原作者为

	Mophie 祈祷着你今后的人生，永远都会有幸福的魔法相伴。

搬运于2025-08-24 22:12:49，当前版本为作者最后更新于2019-11-10 09:28:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

update:修改了格式

这道题点进来的大佬 $100$ 都会做，这里给大家简述一些奇怪的做法......

Part1.水的不行的算法

先看一看这道题，他说了在第i个位置上可以选择跳到 $i-k$ ~ $i+k$ ;

那么我们只需要暴力枚举什么时候会跳即可，即枚举 $i$ ，然后再往下做，时间复杂度 $O(n^2m)$ 。

此算法竟然得 $40$ 分。

Part2.part1的优化

再仔细看一眼题面，发现每一条路径非负，所以——

跳的越远越好

话说为什么非负就跳的越远越好呢？

即得易证显然
可见如上平凡
留作习题答案略
读者自证不难

所以每次即从 $i$ 跳到 $i+k$ 即可

时间复杂度为 $O(n^2)$

此算法得 $80$ 分

Part3.1小小的优化

其实想到Part2就离Part3不远了（反正 $80$ 分对我这种蒟蒻来讲足够了）

首先需要思考的是：我到底我是谁，我在哪，我在干什么是在算什么；

首先先枚举i，再算1->i的路径和，再计算i+k+1->n的路径和；

灵光一闪

其实不就是算 $i+1->i+k$ 之间的距离与 $1->n$ 之间的距离差嘛

所以只需枚举 $i+1->i+k$ 即可，时间复杂度为 $O(nk)$

虽然一分也没有多拿到

Part3.2诡异的满分优化

由Part3得：枚举 $i+1->i+k$ 即可；

那么上一个是 $i->i+k-1$ ;

只需上一个减去 $i->i+1$ 加上 $i+k-1->i+k$ 不就好了吗？

其时间复杂度为 $O(n)$

此算法得 $100$ 分，代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000001],k,Max,now,cnt;
int main() 
{
	cin>>n>>k;
	for(int i=1;i<=n-1;i++)
	{
		cin>>a[i];
		cnt+=a[i];
	}
	for(int i=1;i<=k;i++)Max+=a[i],now+=a[i];
	for(int i=2;i<=n-k;i++)
	{
		now=now-a[i-1]+a[i+k-1];//i+1->i+k
		Max=max(Max,now);
	}
	cout<<cnt-Max<<endl;
	return 0; 
}

Part3.3前缀和优化

只需算 $i+1->i+k$ 即可

那么即为 $1->i+k$ 减去 $1->i$ ;

自然而然的想到了前缀和优化

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long sum[1000001];
long long n,k;
int main()
{
	cin>>n>>k;
	if(k>=n-1)
	{
		cout<<0<<endl;
		return 0;
	} 
	for(int i=1;i<=n-1;i++)
	{
		long long x;
		cin>>x;
		sum[i]=sum[i-1]+x;//前缀和
	}
	long long cnt=sum[k];
	for(int i=2;i<=n-k;i++)
	{
		cnt=max(cnt,sum[i+k-1]-sum[i-1]);//i->i+k-1
	}
	cout<<sum[n-1]-cnt<<endl;
	return 0;
}

Part4：dp党的福利——万物皆可dp

话说此题 $dp$ 也不难想

根据Part3可得每次跳k最优；

那么 $dp$ 公式就出来了

$dp[i][0]$ 表示第i个包括前面都不跳

$dp[i][1]$ 表示第i个跳

则状态转移公式就出来了

$dp[i][0]=dp[i-1][0]+a[i]$;

$dp[i][1]=dp[i-k][0]$$(i>=k)$

再扫一遍即可~

故代码如下：

#include<bits/stdc++.h>
using namespace std;
long long dp[1000009][2],a[1000009],ans;
int n,k;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n-1;i++)
	{
		cin>>a[i];
	}
	for(int i=2;i<=n;i++)
	{
		dp[i][0]=dp[i-1][0]+a[i-1];
		if(i>k)dp[i][1]=dp[i-k][0];
		dp[i][1]=min(dp[i-1][1]+a[i-1],dp[i][1]);//状态转移方程
	}
	cout<<dp[n][1]<<endl;//输出
	return 0;
} 

Part5.尾声

1.开long long！开long long！开long long！

重要的事情说三遍......

2.感谢这一次的出题组为我们这群蒟蒻带来质量如此之高的题，让本蒟蒻有了收获

3.话说dp做法是我在写时想出来的，喜欢吗？