链接：
http://exam.upc.edu.cn/problem.php?id=3135
题目：
题目描述
hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,…xk为开，其他开关为关时，密码锁才会打开。 他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<） 本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有的钱他哪里能逃过被chenzeyu97 NTR的命运？>_< 于是，他为了虐爆czy，也为了去泡更多的妹子，决定打开这把锁。但是他那么神的人根本不屑这种”水题”。于是，他找到了你。 你的任务很简单，求出最少需要多少步才能打开密码锁，或者如果无解的话，请输出-1。
输入
第1行，三个正整数N，K，M，如题目所述。 第2行，K个正整数，表示开关x1,x2,x3..xk必须为开，保证x两两不同。 第三行，M个正整数，表示size[i]，size[]可能有重复元素。
输出
输出答案，无解输出-1。
样例输入
10 8 2
1 2 3 5 6 7 8 9
3 5
样例输出
2
提示
对于50%的数据，1≤N≤20，1≤k≤5，1≤m≤3; 对于另外20%的数据，1≤N≤10000，1≤k≤5,1≤m≤30; 对于100%的数据，1≤N≤10000，1≤k≤10，1≤m≤100。
思路：
假设最终状态是：1 1 1 0 1 0 差分一下： 1 0 0 1 1 1 四个1分别出现在1，4，5，6四个位置，代表
[1,4)
[
1
,
4
)
和
[5,6)
[
5
,
6
)
这两个区间里的数都是1。 先处理出每一段区间全部变成1所需要的最少操作数，然后我们可以发现，取反这两个区间和取反
[1,5)
[
1
,
5
)
，
[4,6)
[
4
,
6
)
这两个区间是等价的，所以这些数可以随机两两组合来进行变换，每次变换的加起来就是这种方案的操作数。
实现：
#include <bits/stdc++.h>
const int inf =
0x3f3f3f3f, maxn =
int(
1e4) +
7, maxm =
int(
2e6) +
7, cache =
1 <<
16;
char buf[cache];
size_t curl, curr;
inline char get() {
if (curl == curr) { curl =
0, curr = fread(buf,
1, cache, stdin);
if (curr == curl)
return EOF; }
return buf[curl++];
}
inline int read(
int x =
0,
char c =
'0') {
do c = get();
while (!
isdigit(c)); x = c ^
'0';
while (
isdigit(c = get())) x = x *
10 + (c ^
'0');
return x;
}
int n, k, m, cnt, dist[maxn], dp[maxm], mp[
27][
27], a[maxn], sz[maxn], num[maxn];
bool mark[maxn], vis[maxn];
std::
queue<int> que;
void bfs(
int x,
int now =
0) {
memset(vis,
0,
sizeof(vis));
dist[x] =
0, vis[x] =
true;
que.push(x);
while (!que.empty()) {
now = que.front(), que.pop();
for (
int i =
1; i <= m; i++) {
if (now + sz[i] <= n && (!vis[now + sz[i]])) {
vis[now + sz[i]] =
true;
dist[now + sz[i]] = dist[now] +
1;
que.push(now + sz[i]);
}
if (now - sz[i] >
0 && (!vis[now - sz[i]])) {
vis[now - sz[i]] =
true;
dist[now - sz[i]] = dist[now] +
1;
que.push(now - sz[i]);
}
}
}
for (
int i =
1; i <= n; i++)
if (num[i]) mp[num[x]][num[i]] = vis[i] ? dist[i] : inf;
}
int dfs(
int x,
int st =
0) {
if (!x)
return 0;
if (~dp[x])
return dp[x];
dp[x] = inf;
for (
int i =
1; i <= cnt; i++)
if (x & (
1 << (i -
1))) {
if (!st) st = i;
else if (mp[st][i] != inf) dp[x] =
std::min(dp[x], dfs(x ^ (
1 << (st -
1)) ^ (
1 << (i -
1))) + mp[st][i]);
}
return dp[x];
}
int main() {
memset(dp, -
1,
sizeof(dp));
n = read(), k = read(), m = read();
for (
int i =
1; i <= k; i++) mark[a[i] = read()] =
true;
for (
int i =
1; i <= m; i++) sz[i] = read();
for (
int i = ++n; i; i--) mark[i] ^= mark[i -
1];
for (
int i =
1; i <= n; i++)
if (mark[i]) num[i] = ++cnt;
for (
int i =
1; i <= n; i++)
if (mark[i]) bfs(i);
printf(
"%d\n", dfs((
1 << cnt) -
1) == inf ? -
1 : dp[(
1 << cnt) -
1]);
return 0;
}
