自动搬运

查看原文

来自洛谷，原作者为

	Clare613 csacademy.com||宣:https://www.luogu.com.cn/team/103922||250粉后橙名就别找我了||目标一：黄+绿+蓝+紫+黑->431/888||目标二：2025J：320+，2025S:250+||个人题库已满

搬运于2025-08-24 23:13:35，当前版本为作者最后更新于2025-04-14 22:43:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题外话

本人十分喜欢鸭子，看到后就忍不住想发一篇。

思路

最开始 $d$ 只鸭子在一号点，也就是说一号点已经被按下了，那么接下来只要把 $2$ 到 $n$ 的点按下就好了。
很明显，我们肯定不会让鸭子走回头路，那么就是一直保证后面的点的上一个点一定有足够的鸭子保证后面的点全都能按下。
于是我们只要从后往前取最大值，再从 $2$ 到 $n$ 加起来输出就行了。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005],maxn[200005],ans;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,d;
    cin>>n>>d;
    for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=n;i>=1;i--){
		maxn[i]=max(maxn[i+1],a[i]);
	}
	for(int i=2;i<=n;i++){
		ans+=maxn[i];
	}
	cout<<ans;
	return 0;
}