首页 > 代码库 > hdu 2147 kiki's game（DP(SG)打表找规律）
hdu 2147 kiki's game（DP(SG)打表找规律）
题意：
n*m的棋盘，一枚硬币右上角，每人每次可将硬币移向三个方向之一（一格单位）：左边，下边，左下边。
无法移动硬币的人负。
给出n和m，问，先手胜还是后手胜。
数据范围：
n, m (0<n,m<=2000)
思路：
dp[i][j]=0，说明从（i,j）这个点到时左下角先手败。dp[i][j]=1则先手胜。
然后记忆搜。但是记忆搜会超时。
搜完把整张表打出来，发现规律了，，，，然后，，，代码剩几行了。
代码：
///打表观察/*int f[2005][2005];int go(int n,int m){ //0:必败 1:必胜 if(f[n][m]!=-1) return f[n][m]; int a1 = n-1, b1 = m; int a2 = n, b2 = m-1; int a3 = n-1,b3 = m-1; if(a1>=1 && b1>=1 && go(a1,b1)==1) return f[n][m] = 0; if(a2>=1 && b2>=1 && go(a2,b2)==1) return f[n][m] = 0; if(a3>=1 && b3>=1 && go(a3,b3)==1) return f[n][m] = 0; return f[n][m] = 1;}*/int main(){ int n,m; while(scanf("%d%d",&n,&m),n||m){ /* rep(i,1,n) rep(j,1,m) f[i][j] = -1; f[1][1] = 0; go(n,m); rep(i,1,n){ rep(j,1,m) printf("%d",f[i][j]); cout<<endl; } */ if(n%2 && m%2) puts("What a pity!"); else puts("Wonderful!"); }}
hdu 2147 kiki's game（DP(SG)打表找规律）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。