题解：AT_arc194_a [ARC194A] Operations on a Stack

cold_jelly · 2025-03-14 10:39:32 · 题解

题意

给定一个长度为 n 的序列 \{a_n\} 和一个初始为空的栈 S，对于每个 i\in [1,n]，依次进行下面两种操作中的其中一种：

• 将 a_i 推入栈顶；
• 如果栈不为空，将栈顶元素删除。（注意：删除后并不将 a_i 推入栈顶）

完成所有操作后，求最终可能得到的栈 S 中所有元素之和的最大值。

思路分析

简单 DP。

令 f_i 表示操作已经进行完 a_i 时栈 S 内元素之和的最大值。

显然，我们要求的答案就是 f_n，初始状态就是 f_0=0（栈为空时元素和为 0），f_1=a_1。

从 f_{i-1} 转移到 f_i 的方式把题意翻译一下就出来了：

• 如果我们选择操作 1，那么 f_i=f_{i-1}+a_i；
• 如果我们选择操作 2，即只删除栈顶元素，那么 f_i 就等价于我们上一次操作不选 a_{i-1} 的值，即 f_{i-2}。

上面两种情况取个最大值就行了。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N], f[N];
signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        scanf("%lld", &a[i]);
    f[0] = 1, f[1] = a[1];
    for(int i = 2; i <= n; i ++)
        f[i] = max(f[i - 1] + a[i], f[i - 2]);
    cout << f[n];
    return 0;
}