描述
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--;
}
}
标签:游戏,硬币,int,tt,赢家,DP,include,dp From: https://blog.csdn.net/2301_78848414/article/details/143479587