題目意思： 給你石頭的數量n，然後給你m個數，每個數表示每次可以拿的石頭的數量，其中一定有一個數為1。 有兩個人玩游戲，依次從石頭堆裡取上面m個數中的一個，拿走該數量的石頭，最後拿完石頭的那個人贏，問誰贏。每個人每一步都是朝最有利於自己贏的數量拿。 解題思路： 看成是一個dp問題，dp[i]=1表示當有i個石頭時，先拿的人贏，dp[i]=2表示先拿的人輸。 依次對m個可拿的石頭數量試探，當有一種拿法使得去掉該數量石頭後是先負狀態，則此狀態為先贏狀態。實際上是一個博弈問題。www.2cto.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; }
