状压DP

状压dp一定要注意位运算的优先级问题(从上到下优先级降低)

(),[ ]

/,*,\%

+ ,-

<<,>>

>,>=,<,<=

==,!=

\&

\hat{}

|

\&\&

||

+=,-=,\&=,\hat{}=,|=,

摸鱼

蜗蜗一共有 n 天假期，在假期的第 i 天摸鱼他会得到 a[i] 的快乐值。如果蜗蜗每天都摸鱼的话，他会有愧疚感，所以蜗蜗制定了这么个计划：对于每一天，蜗蜗都有一个列表，如果蜗蜗在列表中的每一天都在摸鱼的话，这一天蜗蜗就不能摸鱼。现在请问蜗蜗如何摸鱼，使得他能获得的快乐值总和最大？请求出快乐值总和最大是多少。

每一组方案可以用一个长度为n的二进制字符串来表示（1表示摸鱼，0表示不摸鱼），例如当n=5时，10111表示在第1,3,4,5天摸鱼。

有n个数位的二进制字符串可以和十进制[1,2^n]转换，所以枚举十进制数字就可以知道具体在哪一天摸鱼了

遍历每一种摸鱼的情况，把每一天的摸鱼情况用数组b[i]表示，b[i]表示在第i天是否摸鱼

因为蜗蜗有一个列表，如果蜗蜗在列表中的每一天都在摸鱼的话，这一天蜗蜗就不能摸鱼，所以还要判断蜗蜗在数组b的摸鱼状态下，在第i天是否还能摸鱼，

用数组s记录列表中的每种状态，用十进制来表示二进制下每天摸不摸鱼；对于第i天，如果s[i]&i==s[i]；那么根据题意，这一天就不能摸鱼。

int n, a[21], l[21], s[21], b[21];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &l[i]);
        for (int j = 1; j <= l[i]; j++) {
            int x; cin >> x;
            s[i] |= 1 << (x - 1);//记录s[i]
        }
    }
    int ans = 0;
    for (int i = 1; i <= 1 << n; i++) {//枚举每一种摸鱼的情况
        for (int j = 1, k = i; j <= n; j++, k /= 2) {//计算b[i]
            if (k & 1) b[j] = 1;
            else b[j] = 0;
        }
        bool ok = true;
        for (int j = 1; j <= n; j++) {//判断这一天能不能摸鱼
            if (b[j] && l[j] && (i & s[j]) == s[j]) {
                ok = false;
            }
        }
        if (!ok) continue;
        int res = 0;
        for (int j = 1; j <= n; j++) {
            if (b[j]) res += a[j];
        }
        ans = max(ans, res);
    }
    printf("%d", ans);
    return 0;
}

旅行商

蜗蜗的世界里有 n 个城市，城市两两之间通过高速公路连接，从第 i 个城市走到第 j 个城市需要花费 a[i][j] 的时间。

现在蜗蜗想从 1 号城市出发旅游，他想把每个城市都玩个遍，但又不想在一个城市玩两遍，玩完以后蜗蜗需要回到 1 号城市应付期末考试。请问蜗蜗最少需要花费多少时间？

蜗蜗到了一个城市以后，一定会在这个城市游玩。蜗蜗在出发之前会先在 1 号城市游玩。连接两个城市的高速公路不会经过其他城市。由于路况的原因，从第 i 个城市走到第 j 个城市花费的时间不一定等于从第 j 个城市走到第 i 个城市花费的时间。

在之前的旅途中，去过的城市的顺序是不重要的，于是我们可以用f[i][j]表示去过的城市的状态是i（i记录哪些城市去过，哪些城市没去过），现在在j号城市花费的最短时间。

用长度为n的二进制字符串记录，从左往右第x个位置表示蜗蜗有没有去过x号城市，1表示去过，0表示没去过，就可以用十进制数字表示去过的城市状态了。

最后答案等于min_{2\leq j\leq n}(f[2^n-1][j]+a[j][1])

具体实现为：枚举每种状态，依次遍历每个位置j，如果f[i][j] < 1 << 30,说明j城市没有去过，然后考虑从j到k转移

int n, a[19][19], f[1 << 18][19];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    memset(f, 127, sizeof(f));
    f[1][1] = 0;
    for (int i = 1; i < (1 << n); i++) {
        for (int j = 1; j <= n; j++) {
            if (f[i][j] < 1 << 30) {
                for (int k = 1; k <= n; k++) {
                    if (!(i & (1 << (k - 1))))
                        f[i + (1 << (k - 1))][k] = min(f[i + (1 << (k - 1))][k], f[i][j] + a[j][k]);
                }
            }
        }
    }
    int ans = INF;
    for (int i = 2; i <= n; i++) {
        ans = min(ans, f[(1 << n) - 1][i] + a[i][1]);
    }
    printf("%d", ans);
    return 0;
}

消除

桌面上有 n 个方块，蜗蜗想把它们都消除掉。每个方块有个权值，第 i 个方块的权值等于 a[i]。每一次消除蜗蜗有两种选择：

1.选择一个还没有被消除的方块 i，付出 a[i] 的代价把它消除；

2.选择两个还没有被消除的方块 i,j(i≠j)，付出 a[i] xor a[j] 的代价把它们消除；

请问蜗蜗最少需要花费多少代价，能把 n 个方块都消除掉？

用一个长度为n的二进制字符串记录，从右往左第x个位置表示第x个方块有没有被消除（1表示被消除，0表示没有被消除）

int n, a[21], f[1 << 20];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    memset(f, 127, sizeof(f));
    f[0] = 0;
    for (int i = 0; i < (1 << n); i++) {//枚举每一种情况
        for (int j = 1; j <= n; j++) {//当前删除j
            if (!(i & (1 << (j - 1)))) {//判断j是否已经被删除
                f[i + (1 << (j - 1))] = min(f[i + (1 << (j - 1))], f[i] + a[j]);//删除j
                for (int k = j + 1; k <= n; k++) {//删除j和k
                    if (!(i & (1 << (k - 1))))//判断k是否被删除
                        f[i + (1 << (j - 1)) + (1 << (k - 1))] = min(f[i + (1 << (j - 1)) + (1 << (k - 1))], f[i] + (a[j] ^ a[k]));
                }
            }
        }
    }
    printf("%d", f[(1 << n) - 1]);
    return 0;
}

实际上，对于一个状态i，我们优先消除编号最小的没有被消除的方块就可以了；其他的情况在别的状态下会考虑到

非常巧妙

int n, a[21], f[1 << 20];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    memset(f, 127, sizeof(f));
    f[0] = 0;
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 1; j <= n; j++) {
            if (!(i & (1 << (j - 1)))) {
                f[i + (1 << (j - 1))] = min(f[i + (1 << (j - 1))], f[i] + a[j]);
                for (int k = j + 1; k <= n; k++) {
                    if (!(i & (1 << (k - 1))))
                        f[i + (1 << (j - 1)) + (1 << (k - 1))] = min(f[i + (1 << (j - 1)) + (1 << (k - 1))], f[i] + (a[j] ^ a[k]));
                }
                break;//与上一个代码的区别只是多加了一个break;找到编号最小的没有被消除的方块处理后就跳出
            }
        }
    }
    printf("%d", f[(1 << n) - 1]);
    return 0;
}

麦当劳

喜欢吃麦当劳的蜗蜗要在学校呆 n 天，如果第 i 天蜗蜗吃到了麦当劳，他可以获得 a[i] 点快乐值。然而蜗蜗不能吃太多麦当劳，在连续的 m 天中，他最多只能有一半的天数吃麦当劳。请问蜗蜗在这 n 天中最多可以得到多少快乐值？

由于n太大了，所以直接枚举n肯定不行，由于m很小，所以我们用f[1<<m]进行状态转移，对于第i天，我们只需要从第i天开始往左数m天每天吃不吃麦当劳就可以了

用f[i][j]表示考虑到第i天，最近m天每天吃不吃麦当劳的状态为j（j记录了这m天中哪些天吃了麦当劳，哪些天没吃）的情况下最大快乐值是多少

j可以用二进制字符串表示

当i变成i+1时，j/2即可，在根据第i+1天吃不吃麦当劳，考虑是否加上(1 << (m - 1))

int n, m, f[256], v[256], a[100001];
bool b[256];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    memset(b, false, sizeof(b));
    for (int i = 0; i < 1 << m; i++) {
        int cnt = 0;
        for (int j = 0; j < m; j++) 
            if (i & (1 << j)) cnt++;
        if (cnt <= m / 2) b[i] = true;
    }
    memset(f, 128, sizeof(f));
    f[0] = 0;
    for (int i= 1; i <= n; i++) {
        memset(v, 128, sizeof(v));
        for (int j = 0; j < 1 << m; j++) {
            if (f[j] >= 0) {
                v[j / 2] = max(v[j / 2], f[j]);//第i天不吃麦当劳
                if (b[j / 2 + (1 << (m - 1))])//第i天吃麦当劳
                    v[j / 2 + (1 << (m - 1))] = max(v[j / 2 + (1 << (m - 1))], f[j] + a[i]);
            }
        }
        memcpy(f, v, sizeof(f));
    }
    int ans = 0;
    for (int i = 0; i < 1 << m; i++) {
        ans = max(ans, f[i]);
    }
    printf("%d\n", ans);
}