Codeforces

分析

题目给的操作就是区间异或。考虑将原数组差分，那么我们相当于每次可以将两个距离为 $a_i$ 的位置异或 $1$，然后求从全 $0$ 数组生成原数组的最小步数。

我们将这个东西反过来，变为求原数组的差分数组生成全 $0$ 数组的最小步数。

注意到原数组的差分数组至多有 $20$ 个 $1$，因此可以考虑状压 DP。

设 $dp_{S}$ 表示 $S$ 中的 $1$ 消去的最小步数，可以得到转移
$$
dp_S=\min_{i\in S,j\in S,i\neq j}\left\{dp_{S-\left\{i\right\}-\left\{j\right\}}+dis_{i,j}\right\}
$$
这里的 $dis_{i,j}$ 表示将 $i$ 和 $j$ 位置异或 $1$、其它位置不变的最小步数，可以跑 BFS 求出。

然后剩下的优化就很简单了。注意到 $S$ 中的某个元素（假设是最小的那个）是一定要消去的，所以我们强制 $i$ 为 $S$ 中的第 $1$ 个 $1$，枚举 $j$ 转移即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10,K=20+10;
const int inf=0x3f3f3f3f;

int n,k,m;
int a[N],l[N],id[N],cnt=0;
int vis[N],d[N],dis[K][K],dp[1<<20];

inline void bfs(int s) {
    memset(vis,0,sizeof(vis)),vis[s]=1;
    queue<int> Q; Q.push(s); d[s]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re int i=1;i<=m;++i) { int v;
            v=u-l[i];
            if (v>=1&&!vis[v]) vis[v]=1,d[v]=d[u]+1,Q.push(v);
            v=u+l[i];
            if (v<=n&&!vis[v]) vis[v]=1,d[v]=d[u]+1,Q.push(v);
        }
    }
    for (re int i=1;i<=n;++i)
        if (a[i]) dis[id[s]][id[i]]=vis[i]?d[i]:inf;
}

int main() {
    n=read(),k=read(),m=read();
    for (re int i=1;i<=k;++i) a[read()]=1;
    for (re int i=1;i<=m;++i) l[i]=read();
    for (re int i=++n;i;--i) a[i]^=a[i-1];
    for (re int i=1;i<=n;++i) if (a[i]) id[i]=++cnt;
    for (re int i=1;i<=n;++i) if (a[i]) bfs(i);
    memset(dp,0x3f,sizeof(dp)),dp[0]=0;
    for (re int S=1;S<1<<cnt;++S) {
        int i=0; while (!(S&(1<<i))) ++i;
        for (re int j=i+1;j<cnt;++j) {
            if (!(S&(1<<j))) continue;
            dp[S]=min(dp[S],dp[S^(1<<i)^(1<<j)]+dis[i+1][j+1]);
        }
    }
    printf("%d\n",dp[(1<<cnt)-1]==inf?-1:dp[(1<<cnt)-1]);
    return 0;
}