题解：P12193 [NOISG 2025 Prelim] Ducks And Buttons

Clare613 · 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;
}