UPC-3135 - 密码锁 - 状压DP

链接：

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

样例输出

提示

对于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)$和$[5, 6)$这两个区间里的数都是1。
先处理出每一段区间全部变成1所需要的最少操作数，然后我们可以发现，取反这两个区间和取反$[1,5)$，$[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() {
//    freopen("in.txt", "r", stdin);
    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;
}

UPC-3135 - 密码锁 - 状压DP