UVa:10404 Bachet's Game

发布时间:2017-1-18 15:58:55 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVa:10404 Bachet's Game",主要涉及到UVa:10404 Bachet's Game方面的内容,对于UVa:10404 Bachet's Game感兴趣的同学可以参考一下。

博弈论上的动态规划,1Y。     必胜态:无论之后怎么操作,当前拿石头的人都是一定会赢得游戏胜利。 必败态:无论之后怎么操作,当前拿石头的人都是一定会输掉游戏。   用j表示当前还剩下石头数目(0<=j<=m),ai表示每次可以拿走的个数(1<=i<=m),dp[j]还剩j个石头这个时候拿取石头的人胜负态。   那么有三个结论。  1. 当j==0时,也就是说对手拿走了最后剩下的石头,轮到自己的时候已经没有可拿的了,所以此时拿石头的人是必败态。  2.如果至少有一个ai,有j-ai是必败态,那么j是必胜态。假如说甲的某个操作会导致乙成为必败态,那么甲肯定会执行这个操作,所以甲当前所处的状态就是必胜态。 3. 如果对于所有ai, j-ai都是必胜态,那么j是必败态。假如说甲的所有操作都会导致乙成为必胜态,那么甲此时已经是必败了。   然后从小到大枚举j,就可以用动规解决这个问题了。   我觉得对于dp[j]的含义一定要理解清楚。所谓胜负态是针对当前拿石头的人而非甲或乙,胜负是对整个游戏而言而非局部。   #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; bool dp[1000005]; int a[15]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1; i<=m; ++i)scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); dp[0]=false; for(int i=1; i<=n; ++i) { bool ok=true; for(int j=1; j<=m; ++j) { if(i-a[j]>=0) { if(dp[i-a[j]]==false) ok=false; } } dp[i]=!ok; } if(dp[n]) puts("Stan wins"); else puts("Ollie wins"); } return 0; }  

上一篇:Spring MVC和Struts2的比较
下一篇:10. 搜索操作指南 (4)

相关文章

相关评论