题解：AT_arc194_a [ARC194A] Operations on a Stack

思路：

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

首先，用

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

。

代码：

CPP

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

题解：AT_arc194_a [ARC194A] Operations on a Stack

文章操作

思路：

代码：

相关推荐

评论

题解：AT_arc194_a [ARC194A] Operations on a Stack