硬币游戏赢家 | 动态规划

描述

A和B两人玩硬币游戏。开始共有n个硬币。给定两个数字x和y。在每一步中玩家可以选择x、y或1个硬币。A总是开始比赛。选择最后一枚硬币的玩家获胜。对于给定的n值，假设游戏双方都会按最优的方式选择硬币，判断A是否能赢得游戏。用动态规划求解该问题。

输入

输入一个整数t表示测试用例个数

对于每一个测试用例，输入三个整数n, x, y，表示初始硬币个数，可以选择的硬币个数。

输出

对于每个测试用例，如果A能赢则输出A，否则输出B.

如果输入为0，则算A输，因为A没有可以选择的方案 ，末行有换行

输入样例 1 

2
5 3 4
2 3 4

输出样例 1

A
B

题解：

        题目要求使用动态规划，使用二维DP。其中i是每次能选的数量，j是总和，DP数组是最小选择次数。

        转移方程：

        在j>x的时候就不需要计算第三项。

        关于初始化：

        只能选择1的情况，DP第一行为递增的数列，第一列全为0。

        关于结果：

        当次数为奇数则A获胜，否则B获胜。

        关于特殊情况：

        x,y的顺序似乎是会影响结果，所以要交换重新计算一次？证明不来，但是似乎是会影响结果，如下图所示：

        当x,y顺序不同时DP表的次数的奇偶性有差别，所以都计算一次。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long ll;

int t=0,n=0,i,j,k,x=0,y=0,minnum=0,tt=0;
int dp[101][101]={{0}};
int A=0;

void solution(){
    int i,j;
    for(i=1;i<=n;i++){
        dp[0][i]=i;
    }
    for(i=1;i<3;i++){
        for(j=1;j<=n;j++){
            if(i==1){
                if(j>=x){
                    dp[i][j]=min(dp[i][j-x]+1,dp[i-1][j]);
                }
                else{
                    dp[i][j]=dp[i-1][j];
                }
            }
            else if(i==2){
                if(j>=y){
                    minnum=min(dp[i-1][j],dp[i-2][j]);
                    dp[i][j]=min(dp[i][j-y]+1,minnum);
                }
                else{
                    dp[i][j]=min(dp[i-1][j],dp[i-2][j]);
                }
            }
        }
    }
    /*
    for(i=0;i<3;i++){
        for(j=0;j<=n;j++){
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }
    */
    for(i=0;i<3;i++){
        if(dp[i][n]%2!=0){
            A=1;
        }
    }
}


main()
{
    cin >> t;
    while(t>0){
        cin >> n >> x >> y;
        solution();
        if(tt==0){
            i=x;x=y;y=i;tt=1;
            solution();
        }
        tt=0;
        if(A && n!=0){
            cout<< "A" << "\n";
        }
        else{
            cout << "B" << "\n";
        }
        A=0;
        t--;
    }
}