2020上海高校程序设计竞赛暨第18届上海大学程序设计联赛夏季赛（同步赛）G题 选择

时隔快1个月才回来看这个G题，刚打的时候感觉做出来人的数量很少就没打算看，其实，这是一个思维一维dp，首先，我们把dp[i]表示前i个选i/2
个求和的最大值。 然后我们分俩种情况来看其状态转移，第一种序列下标是奇数的情况他的值是由前一个下标的dp值和前2个下标的dp值+a[当前下标值]取最大值转移过来的，最奇妙的是下标为偶数的情况，因为题中说明不能选相邻的数，所以当我们的下标是偶数时候，我们不选当前值，就是
由从1到当前值区间内所有奇数的和来转移过来，这样我们可以用一个前缀和数组，来统计所有奇数下标的和，这个题就完美解决啦~
因为x必选所以让其加上一个比较大的值，最后还是可以从总值中减去的
下面请看代码把

#include<bits/stdc++.h>
const int maxn = 2e5+10;
long long dp[maxn],n,x,sum[maxn],a[maxn];
//dp代表从1~i选i/2个元素的最大值
//sum来统计下标为奇数的前缀和
//a代表原来序列的值 
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>a[i];
    a[x]+=1e14;//因为x是必选所以让x加上一个较大的值 
    sum[1]=a[1];
    //前缀和数组也方便对dp进行赋初值 
    for(long long i=3;i<=n;i+=2)
    {
        sum[i]=sum[i-2]+a[i];
    } 
    for(long long i=2;i<=n;i++)//从第二个点开始dp 
    {
        if(i%2)//如果是奇数， 我们可以选之前所有的偶数，也可以选当前所有的奇数 
        {
            dp[i]=max(dp[i-1],dp[i-2]+a[i]);
        }
        else{
            dp[i]=max(sum[i-1],dp[i-2]+a[i]);
        }
    }   //同理我们可以选之前所有的奇数，也可以选当前的所有偶数
    //注意这里的奇数和偶数指的下标 
    dp[n]-=1e14;
    cout<<dp[n]<<endl;
}