ARC194A题解

Awsdkl · 2025-03-13 17:01:56 · 题解

考虑动态规划。
首先定义状态 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。

代码

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