uva 10891 game of sum

题目链接

详细请参考刘汝佳《算法竞赛入门经典训练指南》 p67

//2013-05-01-20.40
//uva 10891
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 105;

bool vis[maxn][maxn];
int s[maxn];
int d[maxn][maxn];

int dp(int i, int j)
{
    if (vis[i][j])
        return d[i][j];
    vis[i][j] = true;
    int m = 0;
    for (int k = i+1; k <= j; k++)
        m = min(dp(k,j), m);
    for (int k = i; k < j; k++)
        m = min(dp(i, k), m);
    d[i][j] = s[j] - s[i-1] - m;
    return d[i][j];
}

int main()
{
    int n;
    while (scanf("%d", &n) && n)
    {
        int a;
        s[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d" ,&a);
            s[i] = s[i-1] + a;
        }
        memset(vis, false, sizeof(vis));
        printf("%d\n", 2*dp(1, n) - s[n]);
    }
    return 0;
}