首页 > 代码库 > UVA 1558 - Number Game(博弈dp)
UVA 1558 - Number Game(博弈dp)
UVA 1558 - Number Game
题目链接
题意:20之内的数字,每次可以选一个数字,然后它的倍数,还有其他已选数的倍数组合的数都不能再选,谁先不能选数谁就输了,问赢的方法
思路:利用dp记忆化去求解,要输出方案就枚举第一步即可,状态转移过程中,选中一个数字,相应的变化写成一个函数,然后就是普通的博弈问题了,必胜态之后必有必败态,必败态之后全是必胜态
代码:
#include <stdio.h> #include <string.h> const int N = 1050005; int t, n, w, start, dp[N], ans[25], an; int getnext(int state, int x) { for (int i = x; i <= 20; i += x) if (state&(1<<(i - 2))) state ^= (1<<(i - 2)); for (int i = 2; i <= 20; i++) { if (state&(1<<(i - 2))) { for (int j = x; i - j >= 2; j += x) { if (!(state&(1<<(i - j - 2)))) { state ^= (1<<(i - 2)); break; } } } } return state; } int dfs(int state) { if (dp[state] != -1) return dp[state]; if (state == 0) return dp[state] = 0; for (int i = 2; i <= 20; i++) { if (state&(1<<(i - 2))) { if (dfs(getnext(state, i)) == 0) return dp[state] = 1; } } return dp[state] = 0; } int main() { int cas = 0; scanf("%d", &t); memset(dp, -1, sizeof(dp)); while (t--) { start = 0; an = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &w); start |= (1<<(w - 2)); } for (int i = 2; i <= 20; i++) { if (start&(1<<(i - 2))) { if (dfs(getnext(start, i)) == 0) ans[an++] = i; } } printf("Scenario #%d:\n", ++cas); if (an) { printf("The winning moves are:"); for (int i = 0; i < an; i++) printf(" %d", ans[i]); printf(".\n"); } else printf("There is no winning move.\n"); printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。