题目
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1832
题意
n个数据，A，B两个玩家轮流从两端取1到多个数字，最终数字加和为分数，分数最大的获胜，A为先手，二者都很聪明，求A分数-B分数。
思路
如刘书，
区间DP，明显可以用a[i][j]记录区间[i,j)的先手最大分数。
感想
1. 要像刘一样，在能达到要求之后进一步思考如何减少时间
代码
#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 = ;
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 = ; scanf("%d", &n) == && n; ti++) {
for (int i = ; i < n; i++)scanf("%d", g + i);
for (int i = ; i < n; i++) {
sum[i][i] = ;
for (int j = i + ; j <= n; j++) {
sum[i][j] = sum[i][j - ] + g[j - ];
}
}
for (int len = ; len <= n; len++) {
for (int i = , j = i + len; j <= n; i++, j++) {
a[i][j] = sum[i][j] - min(mnleftA[i][j - ], mnrightA[i + ][j]);
mnleftA[i][j] = min(mnleftA[i][j - ], a[i][j]);
mnrightA[i][j] = min(mnrightA[i + ][j], a[i][j]); }
}
int ans = * a[][n] - sum[][n];
printf("%d\n", ans);
} return ;
}