两个人可以从一个长为n的序列两边开始取石子,只能从任意一边取,且取的个数任意(最少为一个),求两人都在最优策略下的A与B的和的差。
如
N = 5;
序列 1 2 3 4 5 则差为 15;
以 d( 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 );
则d( i,i )依赖的状态是所有在其内比之长度小一的最优状态,
可以采用,长度递增的方式,逐次解决
#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> using namespace std; const int maxn = 110; int d[maxn][maxn],sum[maxn],f[maxn][maxn],g[maxn][maxn]; int Sum(int i,int j){ return sum[j] - sum[i-1]; } int n; int main() { while(scanf("%d",&n)&&n){ memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); f[i][i] = g[i][i] = d[i][i] = x; sum[i]=sum[i-1]+x; } for(int L=1;L<n;L++)//长度增量 for(int i=1;i+L<=n;i++){ int j = i+L; d[i][j] = Sum(i,j) - min(f[i+1][j],min(g[i][j-1],0)); f[i][j] = min(d[i][j],f[i+1][j]);//f(i,j)代表min(d[i][j],d[i+1][j],..d[j][j]),可以递推计算,g[i][j]类似; g[i][j] = min(d[i][j],g[i][j-1]); } printf("%d\n",2*d[1][n]-Sum(1,n)); } return 0; }