狀壓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;
}