首页 > ACM题库 > HDU-杭电 > HDU 4155-The Game of 31-博弈论-[解题报告]HOJ
2015
05-23

HDU 4155-The Game of 31-博弈论-[解题报告]HOJ

The Game of 31

问题描述 :

The game of 31 was a favourite of con artists who rode the railroads in days of yore. The game is played with a deck of 24 cards: four labelled each of 1, 2, 3, 4, 5, 6. The cards in the deck are visible to both players, who alternately withdraw one card from the deck and place it on a pile. The object of the game is to be the last player to lay a card such that the sum of the cards in the pile does not exceed 31. Your task is to determine the eventual winner of a partially played game, assuming each player plays the remainder of the game using a perfect strategy.
For example, in the following game player B wins:
Player A plays 3
Player B plays 5
Player A plays 6
Player B plays 6
Player A plays 5
Player B plays 6

输入:

The input will consist of several lines; each line consists of a sequence of zero or more digits representing a partially completed game. The first digit is player A’s move; the second player B’s move; and so on. You are to complete the game using a perfect strategy for both players and to determine who wins.

输出:

The input will consist of several lines; each line consists of a sequence of zero or more digits representing a partially completed game. The first digit is player A’s move; the second player B’s move; and so on. You are to complete the game using a perfect strategy for both players and to determine who wins.

样例输入:

356656
35665
3566
111126666
552525

样例输出:

356656 B
35665 B
3566 A
111126666 A
552525 A

爆搜吧,数据量不大,没必要用记忆化


/*******************************************************************************
 # Author : Neo Fung
 # Email : [email protected]
 # Last modified: 2012-06-21 17:50
 # Filename: ZOJ1827 HDU4155 The Game of 31.cpp
 # Description : 
 ******************************************************************************/
#ifdef _MSC_VER
#define DEBUG
#define _CRT_SECURE_NO_DEPRECATE
#endif

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
using namespace std;

const int kMAX=10010;
const double kEPS=10E-6;
int num[7];

bool dfs(const int &sum)//是否必败点
{
	if(sum>=31)
		return true;//如果到达本节点时sum大于等于31,则此时加任何数字都是输的,可知本节点是必败点

	for(int i=1;i<=6;++i)
		if(num[i] && sum+i<=31)
		{
			--num[i];
			if(dfs(sum+i))//找到一个后续节点是必败点,则本节点是必胜点
			{
				++num[i];
				return false;
			}
			++num[i];
		}
	return true;//找不到任何后续节点是必败点,则本节点也是比败点
}

int main(void)
{
#ifdef DEBUG  
  freopen("../stdin.txt","r",stdin);
  freopen("../stdout.txt","w",stdout); 
#endif  

  int n;
	char str[kMAX];

  while(~scanf("%s",str))
  {
		int len=strlen(str);
		for(int i=1;i<=6;++i)
			num[i]=4;

		int sum=0;
		for(size_t i=0;i<len;++i)
		{
			--num[str[i]-'0'];
			sum+=str[i]-'0';
		}
		printf("%s ",str);

		if(dfs(sum))
		{
			if(len&1)
				printf("A\n");
			else
				printf("B\n");
		}
    else
    {
      if(len&1)
        printf("B\n");
      else
        printf("A\n");
    }

  }

  return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/neofung/article/details/7683793