2011年成都赛区A题的题解。
这是一道博弈动规题目。
首先，我们把数字分成4类，1,，2，大于1的奇数，大于2的偶数。
一个大于3的奇数是等价于3的，因为，总可以对手减一个，你也减一个，就又变成了一个大于3的奇数或者3，总可以让它变成3。因此所有大于1的奇数都等价于3。同理，所有大于2的偶数等价于4。
所以我们用f[a][b][c][d]表示有a个1，b个2，c个3，d个4是不是一个必胜态，然后动规求解就好了。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-09
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
using namespace std;
bool calced[51][51][51][51];
bool f[51][51][51][51];
int F(int a,int b,int c,int d)
{
if (!calced[a][b][c][d])
{
if (a>=1&&!F(a-1,b,c,d)) f[a][b][c][d]=true;
if (b>=1&&!F(a+1,b-1,c,d)) f[a][b][c][d]=true;
if (c>=1&&!F(a,b+1,c-1,d)) f[a][b][c][d]=true;
if (d>=1&&!F(a,b,c+1,d-1)) f[a][b][c][d]=true;
if (a>=2&&!F(a-2,b+1,c,d)) f[a][b][c][d]=true;
if (b>=2&&!F(a,b-2,c,d+1)) f[a][b][c][d]=true;
if (c>=2&&!F(a,b,c-2,d+1)) f[a][b][c][d]=true;
if (d>=2&&!F(a,b,c,d-2+1)) f[a][b][c][d]=true;
if (a>=1&&b>=1&&!F(a-1,b-1,c+1,d)) f[a][b][c][d]=true;
if (a>=1&&c>=1&&!F(a-1,b,c-1,d+1)) f[a][b][c][d]=true;
if (a>=1&&d>=1&&!F(a-1,b,c+1,d-1)) f[a][b][c][d]=true;
if (b>=1&&c>=1&&!F(a,b-1,c-1+1,d)) f[a][b][c][d]=true;
if (b>=1&&d>=1&&!F(a,b-1,c,d-1+1)) f[a][b][c][d]=true;
if (c>=1&&d>=1&&!F(a,b,c-1+1,d-1)) f[a][b][c][d]=true;
calced[a][b][c][d]=true;
}
return f[a][b][c][d];
}
int main()
{
int TC;
cin>>TC;
for (int tc=1;tc<=TC;tc++)
{
int N,a=0,b=0,c=0,d=0;
cin>>N;
for (int i=0;i<N;i++)
{
int t;
cin>>t;
if (t==1) a++;
else if (t==2) b++;
else if (t%2==1) c++;
else d++;
}
cout<<“Case #”<<tc<<“: “<<(F(a,b,c,d)?“Alice”:“Bob”)<<endl;
}
return 0;
}