题意：有一个长度为n的整数序列，A和B轮流取数，A先取，每次可以从左端或者右端取一个或多个数，所有数都被取完时游戏结束，然后统计每个人取走的所有数字之和作为得分，两人的策略都是使自己的得分尽可能高，并且都足够聪明，求A的得分减去B的得分的结果。
思路：很容易想到一个复杂度是O(n^3)的方法，设dp(i,j)为第i个到第j个数时，先手能获得的最大分数，注意到对于一段整数序列，先手的得分与后手的得分之和就是这段序列和，所以后手的得分就是sum(i,j)-dp(i,j)。那么我们只要枚举先手的每种选择就可以了:dp(i,j)=sum(i,j)-min{ dp(i+1,j),dp(i+2,j).....dp(j,j), dp(i,j-1),dp(i,-2j)....dp(i,i)
,0}。这个算法复杂度是O(n^3)
其实我们可以优化到O(n^2)
但是深入分析后可以知道，我们只要记录f(i,j)=min{dp(i,j),dp(i+1,j).....dp(j,j)}，g(i,j)=min{dp(i,j),dp(i,-1j)....dp(i,i)}就可以了，那么dp(i,j)=min{f(i,j),g(i,j),0}
而f(i,j)=min{f(i+1),dp(i,j)} g(i,j)=min{g(i,j-1),dp(i,j)}。那么这个题目就可以O(n^2)解决了。
总结：以后dp的基础上，观察每次递推所用到的值，如果用到的值本身还可以递推，那么我们就可以优化了
首先来一个O(n^3)的代码
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 105
using namespace std;
int n,sum[MAXN],f[MAXN][MAXN];
int main()
{
sum[0]=0;
while(~scanf("%d",&n) && n)
{
for(int i=1;i<=n;++i) {scanf("%d",&f[i][i]);sum[i]=f[i][i]+sum[i-1];}
for(int k=1;k<n;++k)
for(int i=1;i+k<=n;++i)
{
f[i][i+k]=sum[i+k]-sum[i-1];
for(int p=i;p<i+k;++p) f[i][i+k]=max(sum[i+k]-sum[i-1]-f[p+1][i+k],f[i][i+k]);
for(int p=i+k;p>i;--p) f[i][i+k]=max(sum[i+k]-sum[i-1]-f[i][p-1],f[i][i+k]);
}
printf("%d\n",2*f[1][n]-sum[n]+sum[0]);
}
return 0;
}
下面是O(n^2)的代码
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 105
using namespace std;
int f[MAXN][MAXN],g[MAXN][MAXN],dp[MAXN][MAXN],sum[MAXN],n;
int main()
{
freopen("in.txt","r",stdin);
sum[0]=0;//初始化sum[0]=0
while(~scanf("%d",&n) && n)
{
for(int i=1;i<=n;++i)
{
scanf("%d",&dp[i][i]);//本来是时读入到a[i]的，但是注意到dp[i][i]=a[i],那么直接读入到dp[i][i]省空间
f[i][i]=g[i][i]=dp[i][i];//同理f[i][i]=g[i][i]=dp[i][i]
sum[i]=sum[i-1]+dp[i][i];//sum[i]记录前i个数的和
}
for(int k=1;k<n;++k)
for(int i=1;i+k<=n;++i)
{
int j=i+k;
dp[i][j]=sum[j]-sum[i-1]-min(0,min(f[i+1][j],g[i][j-1]));//dp(i,j)=sum(i,j)-min(g(i,j-1),0,f(i+1,j))
f[i][j]=min(f[i+1][j],dp[i][j]); g[i][j]=min(g[i][j-1],dp[i][j]);
//f(i,j)=min(f(i+1,j),dp(i,j)) //g(i,j)=min(g(i,j-1),dp(i,j))
}
printf("%d\n",2*dp[1][n]-sum[n]);
}
return 0;
}