首页 > 代码库 > SRM 511 DIV1 500pt(DP)
SRM 511 DIV1 500pt(DP)
题目简述
给定n个数,两个人轮流取数,和之前两个人的取的数或起来,谁不能取数或者谁取到的数和之前的数或值为511谁输,问谁能够赢?
题解
刚开始的想法是直接搜,不过需要记录取过的值的状态,2^50显然超时。。。对于当前或值cur,或上一个数num,只有两种情况,要么是 cur|num==cur,
对于这种数,只是把这个状态直接给下一个玩家,起到延缓一步的作用,他们的选取顺序对局面没有影响,可以先全部轮流取掉,如果这种数的个数大于当前已经取的数的数量,那么我们还可以选择这种数,如果选择这个数可以导致下一个局面必败,那么当前这个局面可以必赢。第二种情况就是cur|num!=cur,num肯定是没有取过的,如果存在一个数num导致下一个局面必败,那么当前这个局面也是必胜的。如果下一个局面必胜,那么当前局面就是必输的,我们可以用记忆化搜索实现上述过程~~~
代码:
1 vector<int>card; 2 int dp[55][555], n; 3 int dfs(int th, int mask) 4 { 5 if (mask == 511) return 1; 6 if (th == n) return 0; 7 if (~dp[th][mask]) return dp[th][mask]; 8 int cnt = 0; 9 for (int i = 0; i < n; i++) if ((card[i] | mask ) == mask) cnt++;10 if (cnt > th && !dfs(th + 1, mask)) return dp[th][mask] = 1;11 for (int i = 0; i < n; i++) if ((card[i] | mask ) != mask)12 {13 if (!dfs(th + 1, mask | card[i])) return dp[th][mask] = 1;14 }15 return 0;16 }17 class FiveHundredEleven18 {19 public:20 string theWinner(vector <int> cards)21 {22 card = cards;23 n = card.size();24 memset(dp, -1, sizeof(dp));25 return dfs(0, 0) ? "Fox Ciel" : "Toastman";26 }27 };
SRM 511 DIV1 500pt(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。