Description：

有 $n$ 个灯泡，其中有 $k$ 个不亮，要求把所有灯泡弄亮，每次可以选择一个区间翻转，要求区间长度 $\in S$ ，问把所有灯泡弄亮的最小操作次数。

$1\leqslant n\leqslant 10^4,1\leqslant k\leqslant 10,1\leqslant m\leqslant 100$

Solution：

既然是区间异或，我们就可以把原序列异或差分，那么只有 $a[l]$ 和 $a[r+1]$ 会发生变化，而我们的最终目的是让所有的 $a$ 都变成 $0$ ，那么我们把 $S$ 中所有元素都加一，然后每次就可以取反距离为 $s_i$ 的两个位置的值，这个可以一般图最小权匹配，但是这题并不用，因为 $k$ 非常小，而差分后的序列最多只有 $2k$ 个位置为 $1$ ，我们可以状压这些位置被取反的情况，不难发现操作可以看成将一个 $1$ 移动 $s_i$ 距离，如果两个 $1$ 重合了就抵消，那么我们可以用 $BFS$ 暴力计算出将第 $p$ 个 $1$ 移动到 $i$ 的代价 $d[p][i]$ ，花费复杂度 $O(nmk)$ ，然后就可以状压 $DP$ ，因为最小值一定和某个值一块消掉，那就枚举当前最小值和谁消，然后转移一下就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,k,m;

#define MAXN 10010

int p[MAXN];

int a[MAXN];

#define MAXM 110

int s[MAXM];

#define MAXK 12

int pos[MAXN];

int d[MAXK << 1][MAXN];

void BFS(int v)

{

	queue<int> q;q.push(pos[v]);

	memset(d[v],0x3f,sizeof(d[v]));

	d[v][pos[v]] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = 1;i <= m;++i)

		{

			if(k - s[i] >= 1 && d[v][k - s[i]] > d[v][k] + 1)

			{

				d[v][k - s[i]] = d[v][k] + 1;

				q.push(k - s[i]);

			}

			if(k + s[i] <= n && d[v][k + s[i]] > d[v][k] + 1)

			{

				d[v][k + s[i]] = d[v][k] + 1;

				q.push(k + s[i]);

			}

		}

	}

	return;

}

int bitcnt[1 << (MAXK << 1)];

int f[1 << (MAXK << 1)];

int lg[1 << (MAXK << 1)];

int main()

{

	scanf("%d%d%d",&n,&k,&m);

	for(int i = 1;i <= k;++i)scanf("%d",&p[i]);

	for(int i = 1;i <= k;++i)a[p[i]] = 1;

	for(int i = 1;i <= m;++i)scanf("%d",&s[i]);

	++n;

	for(int i = n;i >= 1;--i)a[i] = a[i] ^ a[i - 1];

	for(int i = 1;i <= n;++i)if(a[i])pos[++pos[0]] = i;

	for(int i = 1;i <= pos[0];++i)BFS(i);

	if(pos[0] % 2 == 1)

	{

		puts("-1");

		return 0;

	}

	int tot = (1 << pos[0]) - 1;

	memset(f,0x3f,sizeof(f));

	f[0] = 0;//cout << "$$$" << endl;

	for(int i = 1;i <= tot;++i)

	{

		bitcnt[i] = bitcnt[i >> 1] + (i & 1);

		lg[i] = lg[i >> 1] + 1;

		if(bitcnt[i] & 1)continue;

		int b = lg[(i & (-i))];

		for(int j = 1;j <= pos[0];++j)

		{

			if(j == b)continue;

			if((i >> (j - 1)) & 1)

			{

				f[i] = min(f[i],f[i ^ (1 << (j - 1)) ^ (1 << (b - 1))] + d[b][pos[j]]);

			}

		}

	}

	if(f[tot] < 0x3f3f3f3f)cout << f[tot] << endl;

	else puts("-1");

	return 0;

}