UVa 10891 - Game of Sum 动态规划，博弈 难度: 0

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
typedef pair<int, int> MyPair;
const int MAXN = 101;
int sum[MAXN][MAXN];
int a[MAXN][MAXN];
int mnleftA[MAXN][MAXN];
int mnrightA[MAXN][MAXN];
int g[MAXN];

int main() {
#ifdef LOCAL_DEBUG
    freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
    //freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
    int n;
    for (int ti = 1; scanf("%d", &n) == 1 && n; ti++) {
        for (int i = 0; i < n; i++)scanf("%d", g + i);
        for (int i = 0; i < n; i++) {
            sum[i][i] = 0;
            for (int j = i + 1; j <= n; j++) {
                sum[i][j] = sum[i][j - 1] + g[j - 1];
            }
        }
        for (int len = 1; len <= n; len++) {
            for (int i = 0, j = i + len; j <= n; i++, j++) {
                a[i][j] = sum[i][j] - min(mnleftA[i][j - 1], mnrightA[i + 1][j]);
                mnleftA[i][j] = min(mnleftA[i][j - 1], a[i][j]);
                mnrightA[i][j] = min(mnrightA[i + 1][j], a[i][j]);

            }
        }
        int ans = 2 * a[0][n] - sum[0][n];
        printf("%d\n", ans);
    }

    return 0;
}