当前位置:编程学习 > C/C++ >>

dp+博弈 uva-10404-Bachet's Game

 
题目意思:
给你石头的数量n,然后给你m个数,每个数表示每次可以拿的石头的数量,其中一定有一个数为1。
有两个人玩游戏,依次从石头堆里取上面m个数中的一个,拿走该数量的石头,最后拿完石头的那个人赢,问谁赢。每个人每一步都是朝最有利于自己赢的数量拿。
 
解题思路:
看成是一个dp问题,dp[i]=1表示当有i个石头时,先拿的人赢,dp[i]=2表示先拿的人输。
依次对m个可拿的石头数量试探,当有一种拿法使得去掉该数量石头后是先负状态,则此状态为先赢状态。实际上是一个博弈问题。www.zzzyk.com
由于n很大,用递归的话,每次保存现场,占用的空间会超,但题目限制时间为6s所以可以用递推代替递归,用时间换空间。
 
代码:
[cpp]  
#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<stack>  
#include<queue>  
#define eps 1e-6  
#define INF (1<<20)  
#define PI acos(-1.0)  
using namespace std;  
  
  
int  dp[1200000]; //dp[i]=1表示先胜状态,dp[i]=2表示先负状态,dp[i]=0表示还没有确定  
int kind[15],n,m;  
  
/*int dfs(int temp)  //既然时间给了6s,可以用时间换空间,用递推代替递归 
 
    if(dp[temp]) 
        return dp[temp]; 
 
    for(int i=1;i<=m&&kind[i]<=temp;i++) 
        if(dfs(temp-kind[i])==2) 
            return dp[temp]=1; 
 
    return dp[temp]=2; 
}*/  
  
int main()  
{  
    while(scanf("%d",&n)!=EOF)  
    {  
        scanf("%d",&m);  
        for(int i=1;i<=m;i++)  
        {  
            scanf("%d",&kind[i]);  
            dp[kind[i]]=1; //直接设为先胜,免得以后考虑  
        }  
        sort(kind+1,kind+m+1);  
        memset(dp,0,sizeof(dp));  
        dp[0]=2;  
        for(int i=1;i<=n;i++) //改成递推就过了,哈哈,递归保存现场占用好多空间  
        {  
            int flag=0;  
            for(int j=1;j<=m&&kind[j]<=i;j++)  
            {  
                 if(dp[i]==0&&dp[i-kind[j]]==2)  
                 {  
                     flag=1;  
                     break;  
                 }  
            }  
            flag?dp[i]=1:dp[i]=2;  
        }  
  
        //int ans=dfs(n);  
  
        dp[n]==1?printf("Stan wins\n"):printf("Ollie wins\n");  
    }  
  
    return 0;  
}  
 
 
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,