题解 P3943 【星空】

· · 题解

位运算：

  1. 1<< i >>1 & num，如果为1说明二进制下num的第i位为1，否则为0

定义：

状压 dp 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

一些方法：

  1. 如果上下行有影响的话，经常设dp_{i,j}，i表示第i行，j表示这一行的状态，可以从dp_{i-1,k}转移，但是要判断是否合法

  2. 通常我们会把2^n-1中情况先预处理出当前行合法的状态，转移时再判断两行是否合法

  3. 如果我对一个状态有所操作，想得到另一个状态，那么我们可以对2^n-1种状态分别进行m次操作连边，跑最短路求出最小操作次数

solution

这道题就和上文所说的第三种情况相符，因为灯只有两种状态，所以我们可以转换成01字符串，进行区间取反操作，进而我们可以联想到前缀差分和。

那么对于修改操作我们如何处理？？？我们发现对于一段区间进行修改，只会修改区间左右端点的两个值，且当灯全部关掉的时候，前缀和全为0。

思路逐渐清晰，因为我们只希望把1变成0，其他多余的操作不需要，所以我们可以把1全部压缩在一起，同时记录一下他们在原数组中的位置，通过给出的区间我们可以组合出另一些区间，这样我们可以预处理出所有能拼凑出的区间和他们所需要的操作次数，灯的所有状态分别进行各种操作并向得出的状态连边，边权为最小操作次数跑最短路即可

code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

#define N maxn


using namespace std;
int read(){
    int x = 1,a = 0;char ch = getchar();
    while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
    while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
    return x*a;
}
const int maxn = 1e6+7,inf = 1e9+7;
queue<int>q;
int n,k,m;
int a[maxn],sum[maxn],s[maxn],cnt,arr[maxn];
int b[maxn],vis[maxn],f[N],dis[N],ins[N];

vector<int>g,w;

void SPFA(int pos)
{
    memset(dis,63,sizeof(dis));
    dis[pos] = 0,ins[pos] = 1;q.push(pos);
    while(!q.empty()) {
        int u = q.front();q.pop();ins[u] = 0;
        for(int i = 0;i < g.size();i ++) {
            int v = u^g[i];
            if(dis[v] > dis[u]+w[i]) {
                dis[v] = dis[u]+w[i];
                if(!ins[v]) {q.push(v);ins[v] = 1;} 
            }
        }
    }
}

int main(){
    n = read(),k = read(),m = read();
    for (int i = 0;i <= n+1;i++) a[i] = 1;
    for (int i = 1;i <= k;i++){
        int x = read();a[x] = 0;
    }
    for (int i = 1;i <= n+1;i++) sum[i] = a[i]^a[i-1];
    for (int i = 1;i <= m;i++) b[i] = read();
    for (int i = 1;i <= n+1;i++){
        if (sum[i] == 1){
            arr[++cnt] = 1;
            s[cnt] = i;
        }
    }
    for (int i = 1;i <= n;i++) f[i] = inf;
    f[0] = 0;q.push(0);vis[0] = 1;
    while(!q.empty()) {
        int u = q.front();q.pop();
        for(int i = 1;i <= m;i ++) {
            if(u+b[i] <= n && vis[u+b[i]] == 0) {
                vis[u+b[i]] = 1,f[u+b[i]] = f[u] + 1;
                q.push(u+b[i]);
            } 
            if(u-b[i] > 0 && vis[u-b[i]] == 0) {
                vis[u-b[i]] = 1,f[u-b[i]] = f[u] + 1;
                q.push(u-b[i]);
            }
        }
    }
    for(int i = 1;i <= cnt;i ++) {
        for(int j = i+1;j <= cnt;j ++) {
            g.push_back((1<<i>>1)^(1<<j>>1));
            w.push_back(f[s[j]-s[i]]);
        }
    }
    SPFA((1<<cnt)-1);
    printf("%d",dis[0]);
    return 0;
}