## 题目链接：

https://www.luogu.org/problemnew/show/P3943

## 题目：

### 样例输入

5 2 2
1 5
3 4

### 样例输出

2

## 思路：

看到成段修改01串，考虑先差分一下，发现对于一次区间操作，如果区间两端同为1，那么这两个1就会消失，如果一端是0一端是1，那么就会交换。

考虑对于某个1，一次以其为端点的区间操作实际上就是把这个1挪到了另一个端点上去，再和那个端点上原有的数字进行异或操作。这样就可以进行类bfs操作预处理出所有的状态，然后进行状压DP。

## 实现：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 40005, maxm = 70, maxk = 20;
int n, k, m, a[maxn], len[maxm], number[maxn], dist[maxk][maxk], step[maxn], cnt = 0, idx[maxn], g[(1 << maxk)];
void spfa(int u) {
memset(step, -1, sizeof(step));
queue<int> que;
que.push(idx[u]);
step[idx[u]] = 0;
while (!que.empty()) {
int tmp_u = que.front();
for (int k = 1; k <= m; k++)
for (int j = -1; j <= 1; j += 2) {
int tmp_v = tmp_u + len[k] * j;
if (tmp_v <= 0 || tmp_v > n || step[tmp_v] != -1) continue;
step[tmp_v] = step[tmp_u] + 1;
que.push(tmp_v);
}
que.pop();
}
for (int v = 1; v <= n; v++) if (number[v] != 0) dist[u][number[v]] = step[v];
}
int x = 0, ch;
do ch = getchar(); while (!isdigit(ch));
do x = x * 10 + (ch ^ '0'); while (ch = getchar(), isdigit(ch));
return x;
}
int main() {
scanf("%d%d%d", &n, &k, &m);
for (int i = 1; i <= k; i++) a[read()] = 1;
for (int i = 1; i <= m; i++) len[i] = read();
n++;
for (int i = 1; i <= n; i++) if (a[i] ^ a[i - 1]) number[i] = ++cnt, idx[cnt] = i;
memset(dist, -1, sizeof(dist));
for (int i = 1; i <= cnt; i++) spfa(i);
memset(g, 0x3f, sizeof(g));
g[0] = 0;
for (int u = 0; u < (1 << cnt); u++) {
for (int i = 1; i <= cnt; i++) if ((u & (1 << i - 1)) == 0)
for (int j = i + 1; j <= cnt; j++) if ((u & (1 << j - 1)) == 0)
if (dist[i][j] != -1) {
int v = ((u | (1 << i - 1)) | (1 << j - 1));
g[v] = min(g[v], g[u] + dist[i][j]);
}
}
printf("%d\n", g[(1 << cnt) - 1]);
return 0;
}