首页 > ACM题库 > HDU-杭电 > HDU 4111-Alice and Bob-动态规划-[解题报告]HOJ
2015
04-16

HDU 4111-Alice and Bob-动态规划-[解题报告]HOJ

Alice and Bob

问题描述 :

Alice and Bob are very smart guys and they like to play all kinds of games in their spare time. The most amazing thing is that they always find the best strategy, and that’s why they feel bored again and again. They just invented a new game, as they usually did.
The rule of the new game is quite simple. At the beginning of the game, they write down N random positive integers, then they take turns (Alice first) to either:
1. Decrease a number by one.
2. Erase any two numbers and write down their sum.
Whenever a number is decreased to 0, it will be erased automatically. The game ends when all numbers are finally erased, and the one who cannot play in his(her) turn loses the game.
Here’s the problem: Who will win the game if both use the best strategy? Find it out quickly, before they get bored of the game again!

输入:

The first line contains an integer T(1 <= T <= 4000), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(1 <= N <= 50).
The next line contains N positive integers A1 ….AN(1 <= Ai <= 1000), represents the numbers they write down at the beginning of the game.

输出:

The first line contains an integer T(1 <= T <= 4000), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(1 <= N <= 50).
The next line contains N positive integers A1 ….AN(1 <= Ai <= 1000), represents the numbers they write down at the beginning of the game.

样例输入:

3
3
1 1 2
2
3 4
3
2 3 5

样例输出:

Case #1: Alice
Case #2: Bob
Case #3: Bob

题意:有n堆石子,一次可以拿走一个石子,或者把一堆石子放在另一个石子上。不能再次操作的人输Alice先拿。问谁赢

思路:当石子个数大于1时,可以把他们放到一堆里+1次的操作数。石子数为1时,单独考虑。

设所有只有一个石子的是A堆,其他的石子可以合并的设为B堆。

每一次操作有:

1、把A堆 的两个石子合并。加入到B堆。

2、把B堆的石子减1

3、把A堆的一个石子加入的B堆

4、把A堆的石子减1

可以用记忆化来实现。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
int dp[59][50009];
int dfs(int z,int s)
{
    if(dp[z][s]!=-1) return dp[z][s];
    if(z==0) return dp[z][s] = s&1;
    if(z==1) return dp[1][s]=1;
    if(s==1) return dp[z][s] = dfs(z+1,0);
    dp[z][s] = 0;
    if(!dfs(z-1,s)) dp[z][s] = 1;///直接拿走1个的
    if(s>1&&!dfs(z,s-1)) dp[z][s] = 1;
    if(s>1&&!dfs(z-1,s+1)) dp[z][s] = 1;
    if(z>1&&!dfs(z-2,s?s+3:s+2)) dp[z][s] = 1;///合并之后加入s里
    return dp[z][s];
}
int main()
{
    freopen("in.txt","r",stdin);
    int cas,T=1,n;
    scanf("%d",&cas);
    memset(dp,-1,sizeof(dp));
    while(cas--)
    {
        scanf("%d",&n);
        int z=0,s=0,t=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&t);
            if(t==1) z++;
            else s+=t+1;
        }if(s>1) s--;
        printf("Case #%d: %s\n",T++,dfs(z,s)?"Alice":"Bob");
    }
    return 0;
}

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

参考:http://blog.csdn.net/binwin20/article/details/8041846


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。