题解 P3943 【星空】
devout
2020-11-30 08:39:09
[题目链接](https://www.luogu.com.cn/problem/P3943)
因为区间取反不太好做,我们可以考虑把它差分一下,这样一次区间修改相当于转化成了两次单点修改。
因为原来的序列里最多只有 $k\leq 8$ 个 $0$,所以差分之后最多只会有 $16$ 个 $1$,而且显然有偶数个 $1$
所以可以考虑状压 $dp$,用 $f[S]$ 表示现在已经消除掉的 $1$ 的集合为 $S$ 的最少操作次数。
$$f[S]=\min\limits_{popcount(S\ xor\ S^\prime)=2}\{f[S^\prime]+calc(S^\prime,S)\}$$
考虑 $calc$ 的计算,我们可以以每一个差分后为 $1$ 的位置为起点做一次 spfa(其实是bfs),然后就可以快速得出 $calc$ 的值了
$\mathcal O(2^{2k}\times(2k)^2)$
```cpp
#include <bits/stdc++.h>
using namespace std;
# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=1e5+5;
template<typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int n,k,m;
int a[N],b[N],p[N],tot;
int f[1<<20];
int dis[N][20];
bool inq[N];
void spfa(int s,int op){
queue<int> q;
dis[s][op]=0;
q.push(s);
inq[s]=true;
while(!q.empty()){
int u=q.front();q.pop();
inq[u]=false;
Rep(i,1,m){
int v=u+b[i];
if(v>n+1)continue;
if(dis[v][op]>dis[u][op]+1){
dis[v][op]=dis[u][op]+1;
if(!inq[v])inq[v]=true,q.push(v);
}
}
Rep(i,1,m){
int v=u-b[i];
if(v<1)continue;
if(dis[v][op]>dis[u][op]+1){
dis[v][op]=dis[u][op]+1;
if(!inq[v])inq[v]=true,q.push(v);
}
}
}
}
int main()
{
memset(f,0x3f,sizeof(f));
memset(dis,0x3f,sizeof(dis));
read(n),read(k),read(m);
Rep(i,1,k){
int x;
read(x);
a[x]=1;
}
Rep(i,1,m)read(b[i]);
Rep(i,1,n+1)if(a[i]^a[i-1])p[tot++]=i;
for(int i=0;i<tot;i++)
spfa(p[i],i);
f[0]=0;
for(int S=0;S<1<<tot;S++)
for(int i=0;i<tot;i++)
if(S>>i&1^1)
for(int j=0;j<tot;j++)
if(i!=j&&S>>j&1^1)
f[S|(1<<i)|(1<<j)]=min(f[S|(1<<i)|(1<<j)],f[S]+dis[p[j]][i]);
printf("%d\n",f[(1<<tot)-1]);
return 0;
}
```