【题解】UVa 10891【Game of Sum】

分析

任意时刻游戏的状态都是原始序列的一段子序列,因此用$d(i,j)$表示原序列的第$i$~$j$个元素组成的子序列,在双方都机智的情况下,先手得分的最大值。
转移方程就是
$!d(i,j)=sum(i,j)-\min(d(i+1,j),d(i+2,j),…,d(j,j),d(j,j-1),…,d(i,i),0)$
然后预处理前缀和即可。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
const int MAXN = 100 + 6;
int S[MAXN],A[MAXN],d[MAXN][MAXN];
bool hash[MAXN][MAXN];

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

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

    return 0;
}