题解：AT_arc194_a [ARC194A] Operations on a Stack

zby0501_ · 2025-03-13 22:23:00 · 题解

思路：

这题不难，就是一个简单动态规划。

首先，用 f_i 表示再选到第 i 位时的最大值。把 a 记为读进去的数组，则 f_1 = a_1。接下来，当弹掉最后一个元素后，即为跳过 a 中的 i-1 个元素，即从前 i-2 个元素中选，所以最大值为 f_{i-2}。加入元素时，最大值为先从前 i-1 中取，再把当前的元素加上，所以答案是 f_{i-1}+a_i。最后 f_i 就是两种情况中取最大值。最后答案就是 f_n。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[200005],n,a[200005];
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    f[1]=a[1];
    for(int i=2;i<=n;++i) f[i]=max(f[i-2],f[i-1]+a[i]);
    cout<<f[n];
    return 0;
}