做题感悟：感觉这题很经典，百度了一下才理解怎么做。
解题思路：
这里设 d( i , j ) 代表原序列的第 i ~ j 个元素组成的序列的子序列，在双方都采取最优策略的情况下，先手得分的最大值。那么，如果先手要获得最大值同时让后手得到最小值，因此： d( i , j ) = sum ( i , j ) - min{ d( i+1, j ) , d( i+2 , j ) …… d( j , j ) , d( i , j - 1 ) , d( i , j - 2 ) …… d(i , i ) , 0 } ,sum( i , j
) 是元素 i 到 j 的数之和，‘ 0 ’ 代表取完所有的数。
进一步的优化：d( i , j ) = sum( i , j ) - min { d( i+1 , j ) , d( i + 2 , j ) ……d( j , j ) , d( i , j - 1 ) ,d(i , j - 2 ) ……d( i , i ) , 0 } ,令 f( i, j ) = min{d( i , j ) ,d( i+1 , j ) , d(
i + 2 , j ) ……d( j , j ) }, g( i , j ) = min{ d( i , j - 1 ) , d( i , j - 1 ) , d( i , j - 2 ) …… d(i , i ) } ,则状态转移方程：d( i , j ) = sum ( i , j ) - min{ f( i+1 , j ) ,g( i, j - 1 ) , 0 } ,这里 f , g 也可以快速递推出来：f( i , j ) = min{ d( i , j ) ,f( i + 1 , j
) } , g( i , j ) =min{ d( i , j ) , g( i ,j - 1 ) } .
代码：
#include<stdio.h>
#include<cmath>
#include<string.h>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stdlib.h>
#define INT long long int
using namespace std ;
const int INF = 99999999 ;
const int MY = 20 + 10 ;
const int MX = 100 + 10 ;
int n ;
int dp[MX][MX],sum[MX] ;
int DP(int x,int y)
{
if(dp[x][y]!=-1) return dp[x][y] ;
int& ans = dp[x][y] ;
ans=0 ;
for(int i=x+1 ;i<=y ;i++)
ans = min(ans,DP(i,y)) ;
for(int i=x ;i<y ;i++)
ans = min(ans,DP(x,i)) ;
ans = sum[y]-sum[x-1]-ans ;
return ans ;
}
int main()
{
int x ;
while(scanf("%d",&n),n)
{
sum[0]=0 ;
for(int i=1 ;i<=n ;i++)
{
scanf("%d",&x) ;
sum[i]=sum[i-1]+x ;
}
memset(dp,-1,sizeof(dp)) ;
cout<<2*DP(1,n)-sum[n]<<endl ;
}
return 0 ;
}
优化代码：
#include<stdio.h>
#include<cmath>
#include<string.h>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stdlib.h>
#define INT __int64
using namespace std ;
const int INF = 99999999 ;
const int MY = 100 + 10 ;
const int MX = (1<<11) + 5 ;
const int mod = 1000000000 + 7 ;
int n ;
int f[MY][MY],g[MY][MY],d[MY][MY],a[MY],S[MY] ;
void DP()
{
for(int i=1 ;i<=n ;i++)
f[i][i]=g[i][i]=d[i][i]=a[i] ;
for(int L=1 ;L<n ;L++)
for(int i=1 ;i+L<=n ;i++)
{
int j = i+L ;
int m = 0 ;
m = min(m , f[i+1][j]) ;
m = min(m , g[i][j-1]) ;
d[i][j]=S[j] - S[i-1] - m ;
f[i][j]=min(d[i][j],f[i+1][j]) ;
g[i][j]=min(d[i][j],g[i][j-1]) ;
}
cout<<2*d[1][n]-S[n]<<endl ;
}
int main()
{
while(scanf("%d",&n),n)
{
S[0]=0 ;
for(int i=1 ;i<=n ;i++)
{
scanf("%d",&a[i]) ;
S[i]=S[i-1]+a[i] ;
}
DP() ;
}
return 0 ;
}