【题解】LuoGu3943：星空

原题传送门
因为这个$k<=8$所以想到状压

主要思想是差分
令灯暗为1，灯亮为0
比如一行灯的情况是
$a:01001100$
那么对应差分数组就是
$b:011010100$
可以发现$a_i=b_{1}xor{b}_{2}xor...xor{b}_i$
然后我对于区间$[l,r]$进行反转操作，在差分数组里的表现是
$b_l=b_{l}xor1,b_{r+1}=b_{r+1}xor1$

问题可以转化为把$b$数组变成全部是0
发现$b$数组1的个数一定是偶数个，且最多$2k$个
可以考虑每次消除两个1，而消除这两个1的代价通过预处理求出，接下来就是状压

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

或者要把$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;
}