状压dp常用位运算

​​ACM-ICPC 2018 南京赛区网络预赛 E. AC Challenge（状压dp）​​

位运算

1.判断一个数字x二进制下第i位是不是等于1。

方法：if ( ( ( 1 << ( i - 1 ) ) & x ) > 0)

将1左移i-1位，相当于制造了一个只有第i位上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0，说明x第i位上是1，反之则是0。
  
2.将一个数字x二进制下第i位更改成1。

方法：x = x | ( 1<<(i-1) )

证明方法与1类似，此处不再重复证明。

3.把一个数字二进制下最靠右的第一个1去掉。

方法：x=x&(x-1)


4.把一个数字二进制下第i位置0

方法： x=x&~(1<<(i-1))      

题目

有 n 个问题需要解决，但是每个一问题都有

个前置问题需要先解决才行。每解决一个问题

花费一个时间，得到的分数位

。问最后能得到最大分数。

分析

用一个数字 i 表示一个状态，一个状态就是已经解决了哪些问题，

i 的第 j 位为 1 代表 i 状态解决了问题 j

转移方程很好写：

，其中 s 代表 i 的第 j 个问题还没解决时。 即

。

枚举所有状态，在状态转移之前要分析当前状态 i 是否合理。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 20 + 5;

int n, a[N], b[N], si, tmp, tt;
vector<int> e[N];               // 存前置题目
int dp[1 << 20], ans = 0;

int main(){
    memset(dp, -INF, sizeof(dp));
    dp[0] = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d %d", &a[i], &b[i], &si);
        for(int j = 1, x; j <= si; j++)
        {
            scanf("%d", &x);
            e[i].push_back(x);
        }
    }
    int s = (1 << n) - 1;
    for(int i = 1; i <= s; i++){          // 对于所有状态
        for(int j = 1; j <= n; j++){      // 判断每一个问题的情况
            if(((1 << (j-1)) & i) == 0)   // 若 i 第 j 位等于 0 
                continue;
            for(int k = 0; k < e[j].size(); k++){   // 当前状态没有符合前置问题
                if(((1 << (e[j][k] - 1)) & i) == 0)     // 直接进行下一个状态 i
                    goto end;
            }
        }
        tmp = i, tt = 0;
        while(tmp){             // 当前状态解决了几个问题，
            if(tmp & 1)         // 相当于算下过了几分钟
                tt++;
            tmp >>= 1;
        }
        for(int j = 1; j <= n; j++){    // 对于 n 个问题
            if(((1 << (j - 1)) & i) == 0)  // 若第 j 位是 0
                continue;
            if(dp[i - (1 << (j-1))] != -INF)
                dp[i] = max(dp[i], dp[i - (1 << (j - 1))] + tt * a[j] + b[j]);
        }
        ans = max(ans, dp[i]);
        end: ;
    }
    printf("%d\n", ans);
    return 0;
}