UVA_10891
一开始想到了极大极小的思路，但觉得这不就变成极大极小搜索了么，后来便没继续往下想。
看了别人的题解后发现果然就是极大极小的博弈思想，只不过由于搜索过程中状态有限而且有些状态是重复的，因此可以用记忆化搜索来降低复杂度。当然也可以用递推形式的动规来做。
以后有想法了之后一定要敢于去实现自己的想法。
如果设f[i][j]表示面临由i到j这样一个石子序列所能取得的最大值，那么f[i][j]=max{sum[i][j]-f[i][k],sum[i][j]-f[k][j],sum}，其中sum[i][j]表示i到j的值的和，f[i][k]中i<=k<j，f[k][j]中i<k<=j。
#include<stdio.h>
#include<string.h>
#define MAXD 110
#define INF 1000000000
int N, a[MAXD], A[MAXD], f[MAXD][MAXD];
int init()
{
int i;
scanf("%d", &N);
if(!N)
return 0;
A[0] = 0;
for(i = 1; i <= N; i ++)
{
scanf("%d", &a[i]);
A[i] = A[i - 1] + a[i];
}
return 1;
}
void solve()
{
int i, j, k, sum;
for(i = 1; i <= N; i ++)
for(j = i + 1; j <= N; j ++)
f[i][j] = -INF;
for(i = 1; i <= N; i ++)
f[i][i] = a[i];
for(k = 1; k < N; k ++)
for(i = 1; i + k <= N; i ++)
{
sum = A[i + k] - A[i - 1];
for(j = i; j < i + k; j ++)
if(sum - f[i][j] > f[i][i + k])
f[i][i + k] = sum - f[i][j];
for(j = i + 1; j <= i + k; j ++)
if(sum - f[j][i + k] > f[i][i + k])
f[i][i + k] = sum - f[j][i + k];
if(sum > f[i][i + k])
f[i][i + k] = sum;
}
printf("%d\n", 2 * f[1][N] - A[N]);
}
int main()
{
while(init())
{
solve();
}
return 0;
}