ACM博弈问题,求给思路

问题描述：

ACM博弈问题,求给思路
Problem Description
Alice
and Bob are playing a game.There are two piles of cards.There are N
cards in each pile,and each card has a score.They take turns
to pick up the top or bottom card from either pile,and the score
of the card will be added to his total score.Alice and Bob are both
clever enough,and will pick up cards to get as many scores as possible.
Do you know how many scores can Alice get if he picks up first?
Input
The first line contains an integer T (T≤100),indicating the number of cases.
Each case contains 3 lines.The first line is the N (N≤20).The second line contains N integer ai (1≤ai≤10000).The third line contains N integer bi (1≤bi≤10000).
Output
For each case,output an integer,indicating the most score Alice can get.
SampleInput
2
1
23
53
3
10 100 20
2 4 3
SampleOutput
53
105

1个回答分类：英语 2014-11-06

问题解答：

我来补答

#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.

展开全文阅读