题解 P3943 【星空】

ModestCoder_ · 2020-09-09 16:29:08 · 题解

因为这个k<=8所以想到状压

主要思想是差分， 令灯暗为1，灯亮为0， 比如一行灯的情况是

那么对应差分数组就是

可以发现a_i=b_1xorb_2xor...xorb_i

然后我对于区间[l,r]进行反转操作，在差分数组里的表现是

问题可以转化为把b数组变成全部是0

发现b数组1的个数一定是偶数个，且最多2k个

可以考虑每次消除两个1，而消除这两个1的代价通过预处理求出，接下来就是状压

如果要把10000001变成全0，但是我只能翻转长度为3、4
可以先00010001表示对[1,3]翻转
再00000000表示对[4,7]翻转
说明对于两个相差为x的1，要把他俩变成0，选择x=b1+b2+...+by
多次翻转组合是可以的

或者要把00110000变成全0，但是我只能翻转长度为3、4
可以先00010010表示对[3,6]翻转
再00000000表示对[4,6]翻转
说明翻转区间长度之间相减也是可以的

所以对于某一个长度，通过b数组加加减减可以得到自己的长度，针对合理的情况中求出最少翻转次数，通过完全背包求得

Code：

#include <bits/stdc++.h>
#define maxn 40010
#define maxm 100010
using namespace std;
int a[maxn], dp[maxm], cost[maxn], b[maxn], pos[maxn], power[25], tot, n, m, k;

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

int main(){
    n = read(), k = read(), m = read();
    for (int i = 1; i <= k; ++i){
        int x = read();
        a[x] ^= 1, a[x + 1] ^= 1;
    }
    for (int i = 1; i <= n; ++i) cost[i] = 1e9;
    for (int i = 1; i <= m; ++i) b[i] = read();
    for (int i = 1; i <= m; ++i)
        for (int j = b[i]; j <= n; ++j) cost[j] = min(cost[j], cost[j - b[i]] + 1);
    for (int i = 1; i <= m; ++i)
        for (int j = n - b[i]; j >= 0; --j) cost[j] = min(cost[j], cost[j + b[i]] + 1);
    for (int i = 1; i <= n + 1; ++i)
        if (a[i]) pos[++tot] = i;
    power[0] = 1;
    for (int i = 1; i <= 20; ++i) power[i] = power[i - 1] << 1;
    for (int i = 1; i < power[tot]; ++i) dp[i] = 1e9;
    for (int i = 0; i < power[tot]; ++i)
        for (int j = 1; j <= tot; ++j)
            if (!(i & power[j - 1]))
                for (int k = j + 1; k <= tot; ++k)
                    if (!(i & power[k - 1]))
                        dp[i | power[j - 1] | power[k - 1]] = min(dp[i | power[j - 1] | power[k - 1]], dp[i] + cost[pos[k] - pos[j]]);
    printf("%d\n", dp[power[tot] - 1]);
    return 0;
}