题解P3943【星空】

Krystallos · 2019-09-22 17:18:59 · 题解

学状态压缩的时候找到的题，顺便写篇题解

介绍一下要用的干货：位运算状态压缩，差分，背包，DP（好像后两个都是一个东西）

第一步：处理没被点亮的灯泡

非常的水，差分即可。

不同于普通差分数组（就是那个“a的差分数组是d数组，d的前缀和是a数组”），，本题要用的差分数组是“a的差分数组是d数组，d的前缀异或是a数组”。处理方式见下面的代码：

int x;
for (int i = 1; i <= k; i++) {
    scanf("%d", &x);
    d[x] ^= 1;//差分记录
    d[x + 1] ^= 1;
}

第二步：处理可以做到的翻转长度和所需的次数。

背包。但是区间长度可以相减，所以要正反来两遍。

for (int i = 1; i <= l; i++)
    for (int j = v[i]; j <= n; j++)
        w[j] = min(w[j], w[j - v[i]] + 1);//正着背包
for (int i = 1; i <= l; i++)
    for (int j = n - v[i]; j >= 0; j--)
        w[j] = min(w[j], w[j + v[i]] + 1);//反着背包

重磅步骤：螺旋大DP

将要修改的那几个点压缩出来，压成一个int，作为f的下标。

memset(f, inf, sizeof(f));
f[0] = 0;
int s = (1 << p) - 1;
for (int i = 0; i < s; i++) {
    for (int j = 1; j <= p; j++) {
        if ((1 << (j - 1)) & i)
            continue;
        for (int x = j + 1; x <= p; x++) {
            if ((1 << (x - 1)) & i)
                continue;
            f[i | (1 << (j - 1)) | (1 << (x - 1))] = min(f[i | (1 << (j - 1)) | (1 << (x - 1))], f[i] + w[abs(t[x] - t[j])]);
        }
    }
}

最后一步：输出答案

过水直接贴代码：

if (f[s] != inf)
    printf("%d\n", f[s]);
else 
    puts("-1");

接下来是又香又美味的总代码：

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int t[11], v[70], w[40005], a[40005], f[70000];
int main() {
    int n, k, l, p = 0;
    scanf("%d %d %d", &n, &k, &l);
    for (int i = 1; i <= k; i++) {
        int x;
        scanf("%d", &x);
        a[x] ^= 1;
        a[x + 1] ^= 1;
    }
    for (int i = 1; i<= n + 1; i++)
        if (a[i])
            t[++p] = i;
    for (int i = 1; i <= l; i++)
        scanf("%d", &v[i]);
    memset(w, inf, sizeof(w));
    w[0] = 0;
    for (int i = 1; i <= l; i++)
        for (int j = v[i]; j <= n; j++)
            w[j] = min(w[j], w[j - v[i]] + 1);
    for (int i = 1; i <= l; i++)
        for(int j = n - v[i]; j >= 0; j--)
            w[j] = min(w[j], w[j + v[i]] + 1);
    memset(f, inf, sizeof(f));
    f[0] = 0;
    int s = (1 << p) - 1;
    for (int i = 0; i < s; i++) {
        for (int j = 1; j <= p; j++) {
            if ((1 << (j - 1)) & i)
                continue;
            for (int x = j + 1; x <= p; x++) {
                if ((1 << (x - 1)) & i)
                    continue;
                f[i | (1 << (j - 1)) | (1 << (x - 1))] = min(f[i | (1 << (j - 1)) | (1 << (x - 1))], f[i] + w[abs(t[x] - t[j])]);
            }
        }
    }
    if (f[s] != inf)
        printf("%d", f[s]);
    else 
        puts("-1");
}

最后，贴一个优化到极致的滥用位运算装逼的代码（有兴趣的请自行钻研）

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int t[15], v[105], w[40005], a[40005], f[(1 << 21) + 5];
inline int log2(int k) {
    int l = 0, r = 21, mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (k >> mid != 0)
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}
int main() {
    memset(a, 0, sizeof(a));
    int n, k, l, p = 0;
    scanf("%d %d %d", &n, &k, &l);
    int qqq;
    for (int i = 1; i <= k; i++) {
        scanf("%d", &qqq);
        a[qqq] ^= 1;
        a[qqq + 1] ^= 1;
    }
    for (int i = 1; i <= n + 1; i++)
        if (a[i])
            t[++p] = i;
    for (int i = 1; i <= l; i++)
        scanf("%d", v + i);
    for (int i = 1; i <= n; i++)
        w[i] = 0x3f3f3f3f;
    for (int i = 1; i <= l; i++)
        for (int j = v[i]; j <= n; j++)
            w[j] = min(w[j], w[j - v[i]] + 1);
    for (int i = 1; i <= l; i++)
        for (int j = n - v[i]; j >= 0; j--)
            w[j] = min(w[j], w[j + v[i]] + 1);
    unsigned int s = (1 << p) - 1;
    for (int i = 1; i <= s; i++)
        f[i] = 0x3f3f3f3f;
    for (int i = 0; i < s; i++) {
        int q = i ^ s;
        for (int j = q & (-q); j <= q && q; q -= j, j = q & (-q)) {
            int qq = q - j;
            for (int x = qq & (-qq); x <= qq && qq; qq -= x, x = qq & (-qq)) {
                f[i | j | x] = min(f[i | j | x], f[i] + w[abs(t[log2(x)] - t[log2(j)])]);
            }
        }
    }
    if (f[s] != 0x3f3f3f3f)
        printf("%d\n", f[s]);
    else 
        puts("-1");
}