?
题目意思：
给你石头的数量n，然后给你m个数，每个数表示每次可以拿的石头的数量，其中一定有一个数为1。
有两个人玩游戏，依次从石头堆里取上面m个数中的一个，拿走该数量的石头，最后拿完石头的那个人赢，问谁赢。每个人每一步都是朝最有利于自己赢的数量拿。
?
解题思路：
看成是一个dp问题，dp[i]=1表示当有i个石头时，先拿的人赢，dp[i]=2表示先拿的人输。
依次对m个可拿的石头数量试探，当有一种拿法使得去掉该数量石头后是先负状态，则此状态为先赢状态。实际上是一个博弈问题。www.2cto.com
由于n很大，用递归的话，每次保存现场，占用的空间会超，但题目限制时间为6s所以可以用递推代替递归，用时间换空间。
?
代码：
[cpp] ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
#include
#include ?
#include ?
#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; ?
} ?
?
?
?