Description

由于提莫为巡逻准备的蘑菇太多了，多余的蘑菇路上种不下，于是他精心挑选了一些蘑菇拜访他的好朋友小炮

提莫的蘑菇一共有n个，对于编号为i的蘑菇魔力值是ai。蘑菇的魔力值越高，小炮就越喜欢。当然因为二人是好朋友，蘑菇魔力值最低也不会小于0

提莫要与小炮分享这些蘑菇，他们制定了一个因吹斯听的分配规则：

两人按1-n的顺序逐个分配每个蘑菇的归属权

对于一个蘑菇，如果这一轮的分配者将这个蘑菇分给自己，那么下一轮分配权将转让给对方

反之，如果分配者将蘑菇分配给对方，下一轮他还将持有分配权

你可能会以为提莫会让着小炮，不你想多了！爱恶作剧的提莫会尽力让小炮所获得的蘑菇的魔力值的总和尽可能小！（友尽警告

请你帮小炮算算，如果小炮先手分配，他所能获得的蘑菇的魔力值之和的最大值会是多少？

注意：提莫和小炮都足够聪明且均采取最优策略

Input

单组输入

第一行输入一个n，代表物品的数量，1 <= n <= 3e5

第二行输入n个数字a1-an，代表这n个蘑菇的魔力值，0 <= ai <= 1e9

Output

一个数字，小炮所能获得的蘑菇的魔力值之和的最大值。

Sample Input 1

2

10 20

Sample Output 1

20

Hint

对于样例1，小炮可以要走第一个蘑菇，提莫拿走第二个蘑菇，小炮的喜爱程度是10

小炮也可以把第一个蘑菇给提莫，继续持有第二个蘑菇的分配权，然后拿走第二个蘑菇喜爱程度是20

所以小炮能拿到蘑菇的最大喜爱程度是20

Source

2019年集训队选拔赛

思路：基础博弈论dp，因为是最优策略， 那么先手后手都没区别，都是最优的，也就不需要开而二维了。这是一道CF原题改编的，下次找找贴过来。

注：学校的OJ数据范围毒瘤啊，开long long保险一些。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define ll long longconst int maxn = 3e5;ll sum[maxn];ll dp[maxn];ll th[maxn];int main(int argc, char *argv[]) {
    	ll n;	while(~scanf("%lld",&n))		{
    		for(ll i = 1;i<=n;i++)		{
    			scanf("%lld",&th[i]);		}		for(ll i = n;i>=1;i--)		{
    			sum[i] = sum[i + 1] + th[i];			dp[i] = max(dp[i + 1],sum[i + 1] - dp[i + 1] + th[i]);		}		printf("%lld\n",dp[1]);	}	return 0;}