动态规划（Funny Game，cf 731E）

参考代码 blog.csdn.net/sdfzyhx/article/details/52832832

第一步是要确定状态，dp[i]表示前i个缩成一堆的情况下先手的最大值。dp[i]表示前i个缩成一堆很好想，关键是表示什么的值。题目要求求先手的最大值，因此表示此值十分合理。然后是状态转移，自己做的时候不知道该怎么处理两个人，因为一个人的最优解得根据另一个人的最优解才能求出，所以我就想保存两个人的最优解。事实上无论哪个人，面对同一个状态，他的最优决策都是不变的，所以不需要保存两个人，只需要保存最优决策即可。显然我们想得到dp[1]，而dp[n-1]又是显然的，因为根据题目要求，这种情况下必须要选至少2个，而又只剩2个了。因此要用逆推。状态转移方程是dp[i]=max（sum[j]-dp[j]）i+1<=j<=n。

在面对一个状态时，你的决策只能是取2~n-i个，便利一遍，寻一个最大值即可。值为你的和减去对面的最优解。

注意下，对于dp[i]，如何到达这种状态不重要，重要的是现在该怎么做。递推着递推着你就到初始状态了。

可以优化，在dp时顺便记录sum[j]-dp[j]的最大值即可。

代码

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

ll a[maxn];
ll sum[maxn];
ll dp[maxn];

int main()
{
    ll n;
    scanf("%I64d",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%I64d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    ll MAX=sum[n];
    for(ll i=n-1;i;i--)
    {
        dp[i]=MAX;
        MAX=max(MAX,sum[i]-dp[i]);
    }
    printf("%I64d\n",dp[1]);
    return 0;
}