ARC194A题解

考虑动态规划。
首先定义状态

f_{i,0/1}

表示

1

到第

i

个数中，选或不选第

i

个数的最大值。
先考虑

f_{i,1}

的转移。不难想到

f_{i,1} = \max(f_{i-1,1}, f_{i-1,0}) + a_i

。
再考虑

f_{i,0}

的转移。不难发现，要删除只能两个相邻的一起删。而由于不考虑

i

以后的数，

i+1

这个数无法确定选不选，则

i-1

这个数一定不能选，应此推出转移

f_{i,0} = \max(f_{i-2,0}, f_{i-2,1})

。
最后初始值，将

f_{1,0}

和

f_{0,0}

设为

-\infty

。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+5;

ll n;
ll a[MAXN];
ll f[MAXN][2];

int main()
{
	scanf("%lld", &n);
	for(int i = 1;i <= n;i++)
	{
		scanf("%lld", &a[i]);
	}
	f[1][0] = 0xc0c0c0c0c0c0c0c0;
	f[0][0] = 0xc0c0c0c0c0c0c0c0;
	for(int i = 1;i <= n;i++)
	{
		if(i >= 2) f[i][0] = max(f[i-2][0], f[i-2][1]);
		f[i][1] = max(f[i-1][1], f[i-1][0]) + a[i];
	}
	printf("%lld\n", max(f[n][0], f[n][1]));
	return 0;
}

文章操作

代码

相关推荐

评论

ARC194A题解