首页 > 代码库 > Codeforces Round #376 (Div. 2) E. Funny Game

Codeforces Round #376 (Div. 2) E. Funny Game

题解:

预处理前缀和后,

题意就转变成了。对于一个数组a[n],有两个人,第一个人选了第i(i>=2)个数,第二个人必须选第j(j>i)个数。依此循环,知道选了第n个数

求第一个人选的数的总和减去第二个人选的数的总和的最大值

 

分析:

对于第一个人,选了第k个数,那么从第k+1个数开始,要么继续选,要么给第二个人选,第二个人也是如此。

也据是使得a[i1]-a[i2]+a[i3]-a[i4].........最大。。

也就是一个人递推。。但不知道怎么写。。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll a[200010];
int n;

ll solve(int i)
{
    if(i==n) return a[n];
    return max(solve(i+1),a[i]-solve(i+1));
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]+=a[i-1];
    }
    printf("%lld\n",solve(2));
}

 

Codeforces Round #376 (Div. 2) E. Funny Game