UVa UVA 10891 Game of Sum （区间DP）

/**
*      挺水的区间DP
*   dp[i][j] 表示该轮选手在还剩[i,j]的数中按规则选取所能得到的最大收益
*   最大收益也就是相对于当前选手最优决策后在区间[i,j]中使得两选手的差值最大。
*   这样dp[1][n]其实就是所要的答案。
*     如何求dp[1][n]，其实就是个区间dp，从小范围算起到最后1-n范围。
*   再用个sum[n]数组记录前n项和，方便求区间[i,j]的和。
*   具体状态转移方程看代码，和普通的区间dp一样，枚举z = i->j 如何根据游戏规则取最大值 
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#define DEBUG 0
#define INF 0x7fffffff
#define MAXN 105


typedef long long LL;
using namespace std;

int n, sum[MAXN], dp[MAXN][MAXN];

void dp_func()
{
    for(int k = 2; k <= n; k ++)
    {
        for(int i = 1; i <= n - k + 1; i ++)
        {
            int j = i + k - 1, curMax = -INF, ans;
            for(int z = i; z <= j; z ++)
            {
                int cur = sum[z] - sum[i-1] - dp[z+1][j];
                if(cur > curMax) {
                    curMax = cur;
                }
            }
            for(int z = j; z >= i; z --)
            {
                int cur = sum[j] - sum[z-1] - dp[i][z-1];
                if(cur > curMax)
                    curMax = cur;
            }
            dp[i][j] = curMax;
        }
    }

    cout << dp[1][n] << endl;
}

int main()
{
    while(cin >> n && n)
    {
        sum[0] = 0;
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i ++)
        {
            cin >> dp[i][i];
            sum[i] = sum[i-1] + dp[i][i];
        }
        dp_func();
    }
    return 0;
}