AtCoder-ABC162F Select Half

AtCoder-ABC162F Select Half #

题目大意 #

给定长度为 $n$ 的数组 $A$ , 从中选择 $\lfloor \frac{n}{2}\rfloor$ 个不相邻的元素, 求元素和的最大值.

Solution 1 #

数组下标从 $1$ 开始. 设 $dp[i]$ 为前 $i$ 个数中选择 $\lfloor \frac{i}{2}\rfloor$ 个元素可以得到的最大和. 对于 $dp[i]$ , 如果选择了 $A_i$ , 那么最大和为 $dp[i - 2] + A_i$ .当 $i = 2k$ 时, 如果不选 $A_i$ , 那么需要从前 $2k - 1$ 个数中取出 $k$ 个数 , 因为所选数不能相邻, 因此只有一种选法, 即选择 $A_1, A_3, …, A_{2k - 1}$ , 此时和为 $\sum_{i = 1}^{k}A_{2k - 1}$ . 当 $i = 2k + 1$ 时, 如果不选 $A_i$ , 需要从前 $2k$ 个数中选出 $k$ 个不相邻的数, 恰好等于 $dp[2k] = dp[n - 1]$ .

代码如下:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n;
    cin>>n;
    vector<ll> a(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
    }
    vector<ll> dp(n + 1, 0);
    dp[1] = 0;
    ll sum = a[1];
    for (int i = 2; i <= n; i++) {
        dp[i] = (i & 1)? max(dp[i - 1], dp[i - 2] + a[i]): max(sum, dp[i - 2] + a[i]);
        sum += (i & 1)? a[i]: 0;
    }
    cout<<dp[n]<<endl;
    return 0;
}