首页 > 代码库 > HDU 4317 位运算
HDU 4317 位运算
【题意】:
在一个常规的NIM游戏里,你可以在每堆石子拿走任意数量的石子,问求使先手必败的情况下拿走石子数量的最小值。
【知识点】:
位运算,DP
【题解】:
一道精致的位运算的好题目,细节有不少。
具体解释在代码内。
【代码】:
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 #include <cstdlib> 6 #include <climits> 7 #include <algorithm> 8 9 #define wh while10 #define sf scanf11 #define pf printf12 #define clr(abc,z) memset(abc,z,sizeof(abc))13 #define FOR0(i, n) for(int i = 0; i < n; i++)14 #define FOR1(i, n) for(int i = 1; i <= n; i++)15 16 using namespace std;17 18 const int maxb = 1 << 11;19 const int maxn = 25;20 21 int dp[maxn][maxb], s[maxn], a[maxn], t[maxb];22 int n;23 int getbit(int x){24 int ret = 0;25 wh(x){26 ret += (x & 1); x >>= 1;27 }28 return ret;29 }30 31 int main(){32 FOR0(i, maxb) t[i] = getbit(i);33 wh(sf("%d", &n) != EOF){34 FOR0(i, n) sf("%d", &a[i]);35 if(n < 2){36 puts("impossible"); continue;37 }38 int m, ans;39 clr(s, 0);40 FOR1(i, maxn - 1){41 FOR0(j, n)42 if(a[j] & (1 << (i - 1))) s[i - 1] |= (1 << j);43 if(s[i - 1]) m = i + 1;44 }45 clr(dp, 0x3f); ans = dp[0][0]; dp[0][0] = 0;46 //dp[i][k]从右往左第i+1位通过第i位进位得到的1的状态情况47 FOR1(i, m){48 FOR0(j, (1 << n)){49 if(dp[i - 1][j] < ans){50 int tmp = j & s[i - 1]; //j代表进位后得到的位状况51 //s[i - 1]保存原本存在的当前位置的1的状况52 for(int k = tmp; k < (1 << n); k++){53 if(((k & tmp) == tmp)54 //经过右边位置进位得到的状态存在与总状态中55 && (((s[i - 1] ^ j) & (k ^ tmp)) == (k ^ tmp))56 //未经进位得到的状态存在于右边位置中1状态子集内57 && (((t[(s[i - 1] ^ j) ^ (k ^ tmp)] & 1) == 0) || t[(s[i - 1] ^ j) ^ (k ^ tmp)] < n))58 //那些右边状态不进位加1的状态不能包含所有的159 dp[i][k] = min(dp[i][k], dp[i - 1][j] + (t[k ^ tmp] + (t[(s[i - 1] ^ j) ^ (k ^ tmp)] & 1)) * (1 << (i - 1)));60 }61 }62 }63 }64 FOR0(i, (1 << n)){65 if((t[i] & 1) == 0)66 ans = min(ans, dp[m][i]);67 }68 pf("%d\n", ans);69 }70 return 0;71 }
HDU 4317 位运算
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。