poj 4155 The Game of 31 夜

http://acm.hdu.edu.cn/showproblem.php?pid=4155

题目大意：

1,2,3,4,5,6 大小的牌 各有4张

已经选了一些 可能继续选，可能不继续

问谁会赢

思路:

无论该谁选 他的所有可供选择的牌中 只要有一张牌使他胜利（使对方输） 他就会胜利 否则就会输

注意：

输入用scanf（）；

代码及其注释：

#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<queue>

using namespace std;
int sum[8];
char s[26];
int K;
bool dfsb(int );
bool dfsa(int num)
{
   for(int i=6;i>=1;--i)//这里i从6 开始搜是因为 从大数开始搜可以减短搜的层数 总体上提高效率
   {
       if(sum[i]>0&&num+i<=K)//i 可选择
       {
           --sum[i];
           if(dfsb(num+i)==false)//有一个选择使得B输 A就会胜利
           {++sum[i];return true;}
           ++sum[i];
       }
   }
   return false;
}
bool dfsb(int num)
{
   for(int i=6;i>=1;--i)
   {
       if(sum[i]>0&&num+i<=K)
       {
           --sum[i];
           if(dfsa(num+i)==false)
           {++sum[i];return true;}
           ++sum[i];
       }
   }
   return false;
}
int main()
{
    while(scanf("%s",s)!=EOF)
    {
        for(int i=1;i<=6;++i)
        {
            sum[i]=4;//每张牌有四张
        }
        int n=strlen(s);
        K=31;
        int k=0;
        for(int i=0;i<n;++i)
        {
            --sum[s[i]-'0'];//减去已出现的牌
            k=k+(s[i]-'0');//几经达到的大小
        }
        bool awin;//A是否胜利
        if(k>31)//如果几经大于31
        {
            if(n%2==0)//n为偶数说明该A选了 所以是B超出了31 A胜利
            awin=true;
            else
            awin=false;
        }
        else
        {
           if(n%2==0)//n 为偶数则从A开始选择
           {
               if(dfsa(k))
               awin=true;
               else
               awin=false;
           }
           else
           {
               if(dfsb(k))
               awin=false;
               else
               awin=true;
           }
        }
        if(awin)
        {
            printf("%s A\n",s);
        }
        else
        {
            printf("%s B\n",s);
        }

    }
    return 0;
}