题目描述

由于一些原因， Cubercsl 又送了 Compute 一个长度为 n 的数组。

但是 Cubercsl 的兴趣很奇怪，他要求 Compute 从中选恰好 个才能拿走，并且不能选择在数组中相邻的数。

同时，Compute 也有着奇怪的癖好 --- 他一定会选择第 x 个数。

既然能拿，Compute 当然想要越多越好。即他想知道，他能拿走的数的和最大是多少。

具体细节看题目链接

分析

假设 表示前 个数中选择 个的最优选择。
由于奇数选择的个数是和偶数选择个数有略微区别（奇数的一半下取整会失精），因此需要分情况 表示原数组， 表示奇数 的奇数前缀和
由于一定要选择 位置的数，那么给该位置赋一个极大值，那么最后的答案对应的选法就一定是选择了该位置的一种选法~

奇数

对于 为奇数时，可分为两种情况，第一种，选择当前数；第二种不选择当前数.
由于选择不能相邻，因此第一种情况对应 , 第二种情况对应 (由于 (偶数)对应的选择个数和
一样, 同时包含所有不选择当前数的情况)
最终

偶数

对于 为偶数时，也可分为两种情况，第一种，选择当前数；第二种不选择当前数.
由于选择不能相邻，因此第一种情况对应 , 第二种情况对应当前位置截止的前面所有奇数的和（模拟可知，唯一选法）
最终

注：为什么在偶数情况下，第二种情况，不选择当前数所对应的表示不能用 呢? 由于当前 为偶数，选择的数的个数若为num，那么 奇数所对应的 选择的个数将是num - 1, 比需要选择的个数少一个，而此时亦不能选择当前数，因此此项表达不能描述该种情况。

具体AC代码如下

#include "bits/stdc++.h"
#define int long long
using namespace std;
const int N = 1e6 + 1;
const int M = 1e16;
int a[N], dp[N], s[N];
signed main () {
    ios::sync_with_stdio(false);
    int n, x;
    cin >> n >> x;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    a[x] += M, s[1] = a[1]; 
    for (int i = 3; i <= n; i += 2)
        s[i] = s[i - 2] + a[i]; ///求奇数前缀和
    for (int i = 2; i <= n; ++i) { ///第1个位置为奇数选择0个~因此从第2个位置开始
        if (i & 1) dp[i] = max(dp[i - 2] + a[i], dp[i - 1]);///奇数情况
        else dp[i] = max(dp[i - 2] + a[i], s[i - 1]);///偶数情况
    }
    cout << dp[n] - M;
    return 0;
}