题解：AT_arc194_a [ARC194A] Operations on a Stack

题意

给定一个长度为

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}$ 。

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

代码实现

CPP

#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;
}

题解：AT_arc194_a [ARC194A] Operations on a Stack

文章操作

题意

思路分析

代码实现

相关推荐

评论

题解：AT_arc194_a [ARC194A] Operations on a Stack