当前位置: 代码迷 >> 综合 >> 动态规划 状压DP
  详细解决方案

动态规划 状压DP

热度:1   发布时间:2024-01-18 18:37:25.0

一、二进制基础

计算:主要有与&,或|,异或^等。

&:两者均为1则1,否则为0
|:两者均为0则0,否则为1
^:两者相同即为0,否则为1

部分重要计算:

1.判断数字x二进制第i位是否等于1
if(((1<<(i?1))&x)>0)
解释:将1左移i-1位,即1在第i位上,将其与x进行与运算判断是否大于0即判断是否为12.将数字x二进制第i位改成1
x=x|(1<<(i?1))
解释:得到第i位的1,将其或运算3.将数字x二进制最右边的第一个1去掉
x=x&(x?1)

例如:集合中,二进制1010101即表示选取

 

引例:

“......提壶去打酒,遇店加一倍,遇花喝一斗。”

一共遇到5次店,10次花,酒正好喝完,求遇到酒和花的次数的组合可能数。

long long solve(){int ans = 0;for(int i = 0;i < (1<<14); i++) {int tot_1 = 0;int tot_0 = 0;int num = 2;for (int j = 0; j < 14; j++) {if (i&(1<<j)) { // 判断i从右数第j+1位是否为1tot_1++;num = num*2;}else {tot_0++;num = num - 1;}}if(tot_1 == 5 && tot_0 == 9 && num == 1) {++ans;}}return ans;
}

 

二进制枚举

要求实现:在N个数字中找不重复的数字,通过加法凑成X的方案数。

long long solve(int a[],int N,int X) {int ans = 0;for(int i = 0; i < (1<<N);i++) {int num = 0;for(int j = 0; j < N; j++) {if(i&(1<<j)) {num+=a[j];}}if(num == X) ans++;}return ans;
}

状压DP:

在元素规模相对较小(20)且要表示每个元素取或者不取的时候,可以使用。

 

TSP问题(NP-完全):

 

 

  相关解决方案