首页 > 其他分享 >硬币游戏赢家 | 动态规划

硬币游戏赢家 | 动态规划

时间:2024-11-04 11:18:20浏览次数:5  
标签:游戏 硬币 int tt 赢家 DP include dp

描述

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数组是最小选择次数。

        转移方程:

dp[i][j]=min(dp[i-1][j],dp[i-2][j],dp[i][j-x]+1)

        在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

相关文章

  • 手游大佬是怎么推广宣传自己游戏的
    1.手游市场的现状与竞争激烈程度2.推广宣传在手游成功中的关键作用3.文章目的:揭秘手游大佬的推广策略二、精准定位与市场分析1.确定目标用户群体  -用户画像的构建  -用户需求的深入分析2.市场调研与竞品分析  -行业趋势的把握  -竞争对手的推......
  • 2024-11-03:得到更多分数的最少关卡数目。用go语言,Alice 和 Bob 正在进行一个有 n 个关
    2024-11-03:得到更多分数的最少关卡数目。用go语言,Alice和Bob正在进行一个有n个关卡的游戏,其中每个关卡要么是困难模式(possible[i]==0),要么是简单模式(possible[i]==1)。玩家在游戏中获得分数的规则如下:通过简单模式的关卡可得1分,而遇到困难模式的关卡将扣除1分。Alice从......
  • 简易扫雷游戏(C语言)
    扫雷游戏是曾风靡一时的益智小游戏,在此,我们用C语言知识,简单复现一下其基础玩法————,扫雷游戏的实现,需要以下几个基本功能:1,打印菜单2,设置棋盘——> 初始化棋盘3,埋雷4,找雷这些功能在下方我将一一为大家讲解,如何用C语言程序来实现—————在进行基本的写出......
  • 红色警戒2+3游戏合集[共和国之辉][尤里的复仇][世界大战]
    当年爆款游戏红警2让很多人爱上了“建造游戏”有那么一些已经老去的产品,它们也许早已淡出人们的视线,但每每想到却令我们充满回忆。从90年代末到21世纪初的十几年,RTS(即时战略游戏)可以说是游戏市场最为火爆的一种类型,而红色警戒2(Command&Conquer:RedAlert2)绝对是玩家......
  • luoguP2016 战略游戏
    给定一棵n个结点的树,至少要选多少个点才能覆盖所有边?边的两个端点至少有一个被选中则认为覆盖。1<=n<=1500分析:设dp[i][0]表示以i为根的子树,不选i的答案,同理dp[i][1]为选i的答案。自下而上dp,如果选了i,那么其子节点可以选或不选;如果不选i,那么其子节点必须选。#include<bits/std......
  • luoguP1005 矩阵取数游戏
    有n*m的矩阵,每个元素a[i][j]均为非负整数,游戏规则如下:每轮从每行各取一个元素,共n个。经过m轮后取完所有元素。每次取走的元素只能是该元素所在行的行首或行尾。每轮取数都有一个分值,为每行取数的得分之和,每行取数的得分为被取走的元素值乘以2的i次方,其中i为取数轮次,从1开始。......
  • 《漫威复仇者联盟》游戏辅助工具修改器风灵月影版操作教程详解
    《漫威复仇者联盟》是一款基于漫威超级英雄的第三人称动作冒险游戏,玩家可以操控各种超级英雄完成任务和挑战。风灵月影版的修改器为这款游戏提供了多种便捷功能,帮助玩家更轻松地探索游戏世界,提升游戏体验。以下是《漫威复仇者联盟》游戏辅助工具修改器风灵月影版的操作教程详解......
  • C++ 实现俄罗斯方块游戏
    ✅作者简介:2022年博客新星第八。热爱国学的Java后端开发者,修心和技术同步精进。......
  • 【河北建筑工程学院毕业论文】基于Spring Boot架构的游戏商城的设计与实现
    注:仅展示部分文档内容和系统截图,需要完整的视频、代码、文章和安装调试环境请私信up主。摘要随着互联网技术的发展,游戏行业遇到了前所未有的发展和机遇。游戏商城是游戏行业中的一个重要组成部分,为游戏玩家提供了游戏购买、下载、充值等全方位服务。随着游戏用户的快速增......