首页 > 代码库 > poj 2311 Cutting Game （SG）
poj 2311 Cutting Game （SG）
题意：
有一张W*H的纸片。
每人每次可以横着撕或者竖着撕，先撕出1*1那一方胜。
数据范围：
W and H (2 <= W, H <= 200)
思路：
很好抽象出游戏图的模型，用SG解决。直接看代码。
代码：
int dp[maxn][maxn];int sg(int w,int h){ if(dp[w][h]!=-1) return dp[w][h]; bool g[maxn]; mem(g,false); for(int i=2;i<=w/2;++i) g[sg(i,h)^sg(w-i,h)] = true; for(int i=2;i<=h/2;++i) g[sg(w,i)^sg(w,h-i)] = true; for(int i=0;;++i){ if(!g[i]) return dp[w][h]=i; }}int main(){ mem(dp,-1); int w,h; while(scanf("%d%d",&w,&h)!=EOF){ if(sg(w,h)) puts("WIN"); else puts("LOSE"); }}
poj 2311 Cutting Game （SG）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。