UVa 10891 - Game of Sum
传送门
题意
两个人取数字，可以从头开始也可以从尾巴开始，连续，求两个人的最大差值。
参考了某处的解题报告。
虽然想到用$dp[i][j]$表示i到j第一个人得到的最大值，但是轮流取就不知道怎么处理了（ ＴДＴ），所以得不出状态转移方程。
看了解题报告才知道可以把$dp[i][j]$表示成这个范围内能选择的最大数，这些区间可以当成是B能达到的最大值，然后取最小。
。一入DP深似海，从此那啥成路人。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 10;
int dp[MAXN][MAXN], sum[MAXN], vis[MAXN][MAXN];
int DFS(int l, int r)
{
if (vis[l][r])
return dp[l][r];
vis[l][r] = 1;
int temp = 0;
for (int i = l; i < r; i++)
temp = min(DFS(l, i), temp);
for (int i = l + 1; i <= r; i++)
temp = min(DFS(i, r), temp);
return dp[l][r] = sum[r] - sum[l - 1] - temp;
}
int main()
{
//freopen("input.txt", "r", stdin);
int n, i, j;
while (scanf("%d", &n), n)
{
//memset(vis, 0, sizeof vis);
dp[0][0] = 0;
for (i = 1; i <= n; i++)
{
scanf("%d", ∑[i]);
sum[i] += sum[i - 1];
for (j = 1; j <= n; j++)
vis[i][j] = 0;
}
printf("%d\n", 2 * DFS(1, n) - sum[n]);
}
return 0;
}