ACM博弈问题,求给思路

#include<cstdio>#include<algorithm>using namespace std;const int N = 23;int x[N][N][N][N], y[N][N][N][N];int n, A[N], B[N];int main(){ int t; scanf("%d",&t); while(t--) {  scanf("%d",&n);  for (int i = 1;i<=n;i++)  {   scanf("%d",A + i);  }  for (int i = 1;i<=n;i++)  {   scanf("%d",B + i);  }  for (int i = 1;i<=n;i++)//单个牌初始化  {   for (int j = 1;j<=n;j++)   {    x[i][i][j + 1][j] = x[i][i][j][j - 1] = A[i];    y[i][i][j + 1][j] = y[i][i][j][j - 1] = 0;    x[j + 1][j][i][i] = x[j][j - 1][i][i] = B[i];    y[j + 1][j][i][i] = y[j][j - 1][i][i] = 0;   }  }  for (int j = 1;j<=n;j++)//单独处理第二堆的情况  {   for (int M = 1;M < n;M++)   {    for (int i = 1;i<=n;i++)    {     int &X = x[j][j - 1][i][i + M] = -1, &Y = y[j][j - 1][i][i + M] = 1 << 30;     X = max(B[i] + y[j][j + 1][i + 1][i + M], B[i + M] + y[j][j + 1][i + 1][i + M - 1]);     Y = min(x[j][j + 1][i + 1][i + M], x[j][j + 1][i][i + M - 1]);     x[j + 1][j][i][i + M] = X;     y[j + 1][j][i][i + M] = Y;    }   }  }  for (int j = 1;j<=n;j++)//单独处理第一堆的情况  {   for (int N = 1;N < n;N++)   {    for (int i = 1;i<=n;i++)    {     int &X = x[i][i + N][j][j - 1] = -1, &Y = y[i][i + N][j][j - 1] = 1 << 30;     X = max(A[i] + y[i + 1][i + N][j][j - 1], A[i + N] + y[i][i + N - 1][j][j - 1]);     Y = min(x[i + 1][i + N][j][j - 1], x[i][i + N - 1][j][j - 1]);     x[i][i + N][j + 1][j] = X;     y[i][i + N][j + 1][j] = Y;    }   }  }  for (int M = 0;M < n;M++)//同时处理两堆的情况  {   for (int N = 0;N < n;N++)   {    for (int i = 1;i + M<=n;i++)    {     for (int j = 1;j + N<=n;j++)     {      int &X = x[i][i + M][j][j + N] = -1;      int &Y = y[i][i + M][j][j + N] = 1 << 30;      if (i <= i + M)      {       X = max(X, max(A[i] + y[i + 1][i + M][j][j + N], A[i + M] + y[i][i + M - 1][j][j + N]));       Y = min(Y, min(x[i + 1][i + M][j][j + N], x[i][i + M - 1][j][j + N]));      }      if (j <= j + N)      {       X = max(X, max(B[j] + y[i][i + M][j + 1][j + N], B[j + N] + y[i][i + M][j][j + N - 1]));       Y = min(Y, min(x[i][i + M][j + 1][j + N], x[i][i + M][j][j + N - 1]));      }     }    }   }  }  printf("%d\n",x[1][n][1][n]); } return 0;} 动态规划,x[a][b][c][d]表示当前第一堆剩下a到b的牌,第二堆剩下c到d的牌,“先手”先动能获得的最大分数。y[a][b][c][d]表示当前第一堆剩下a到b的牌,第二堆剩下c到d的牌,“后手”先动能获得的最大分数。先预处理出单独一堆的情况,然后在递推出两堆牌同时进行博弈的情况。状态转移很简单的,对于x[a][b][c][d],就是分四种情况考虑,从第一堆选择第a张牌,或者从第一堆选择第b张牌,或者从第二堆选择第c张牌,或者从第二堆选择第d张牌,选牌之后就是沦为后手了,所以就是所选择的牌的分数加上对应的后手状态的分数的最大值。对于y[a][b][c][d],基本同上,只不过因为是后手,所以没有牌的分数而已。上面写法略挫,而且只是过了样例。仅供参考而已o>_<o。