• 状态压缩DP
  • 准备工作
  • 例题 CodeForces 580D. Kefa and Dishes
    • 题目大意
    • 分析

状态压缩DP

状态压缩DP，状压dp的难点在于状态的表示，状态的表示是否是满足无后效性的，是不是满足最优子结构的。是不是可以很容易的通过位运算的特性去用一个状态得到一个新状态。

准备工作

状压dp中少不了对状态的操作。再加上我们一般都会用二进制去表示状态，所以需要对 C++ 中的位运算部分有些了解。

• 判断第i为是否为1 （这个位是从右数起，从0开始。）if (x&(1<<i) {}或者if ((x>>i)&1) {}。 前面两种写法都是可以的，这里要注意不要忘记了位运算两侧的括号。因为位运算的优先级很低。
• 设置第i位为1 x |= 1<<i;
• 设置第i位为0 x &= ~(1<<i);
• 切换第i位 x ^= 1<<i;

例题 CodeForces 580D. Kefa and Dishes

题目大意

有n种菜，选m种。每道菜有一个权值，有些两个菜按顺序挨在一起会有combo的权值加成。求最大权值。

分析

看到题目就会向二进制状态的方向考虑，理由是n和m的数据范围都在20左右，非常小。因为如果用二进制表示状态的话，最大也只能表示20位左右的状态，再多就基本一定会超时了。
在这道题目中，我们的状态表示：$dp[st][i]$，代表了当选用st这样的状态，并且最后一个选择的是第i个菜的时候的最大权值。保存最后的选择，是为了计算combo值，前面的状态就很容易理解了，用1来表示选择了，用0表示没有选择。
状态转移方程上，写了这么多的dp题，应该很容易得到，这部分可以去看代码。

#include <bits/stdc++.h>
using namespace std;  
const int maxn = 20;  
typedef long long LL;

int a[maxn];  
int comb[maxn][maxn];  
LL dp[(1<<18)+10][maxn];  
LL ans = 0;  
int n, m, k;

int Cnt(int st) {  
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (st&(1<<i)) {
            res++;
        }
    }
    return res;
}

int main() {  
    memset(comb, 0, sizeof comb);
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < k; i++) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        x--;
        y--;
        comb[x][y] = c;
    }
    int end = (1<<n);
    memset(dp, 0, sizeof dp);
    for (int st = 0; st < end; st++) {
        for (int i = 0; i < n; i++) {
            if (st&(1<<i)) {
                bool has = false;
                for (int j = 0; j < n; j++) {
                    if (j != i && (st&(1<<j))) {
                        has = true;
                        dp[st][i] = max(dp[st][i], dp[st^(1<<i)][j] + a[i] + comb[j][i]);
                    }
                }
                if (!has) {
                    dp[st][i] = a[i];
                }
            }
            if (Cnt(st) == m) {
                ans = max(ans, dp[st][i]);
            }
        }
    }

    cout << ans << endl;
    return 0;
}