题目

题目描述

$n$枚硬币正面朝上摆成一排，给定$a_1,a_2,\cdots,a_m$，每次操作可以翻转连续$a_i$个硬币。要求经过最少次数的操作，使得仅第$x_1,x_2,\cdots,x_k$枚硬币反面朝上，输出最少次数

输入格式

第一行三个整数$n,k,m$
第二行$k$个整数表示需要反面朝上的硬币位置，从$1$编号
第三行$m$个整数表示$a_1,a_2,\cdots,a_m$

输出格式

一个整数表示答案，若无解，则输出$-1$

样例

样例输入

1
2
3

10 8 2
1 2 3 5 6 7 8 9
3 5

样例输出

数据范围与提示

对于$30\%$的数据，$n,m\leqslant 10$
对于$60\%$的数据，$m\leqslant 20$
对于$100\%$的数据，$1\leqslant n\leqslant 10000,1\leqslant k\leqslant 10,1\leqslant m\leqslant100,1\leqslant a[i]\leqslant n$

题解

因为每次翻转改变的是相邻硬币相对的状态
所以我们用$d_i$表示相邻硬币相对的状态，即$0$表示状态相同，$1$表示状态不同
现在，假设我们翻转$[x+1,x+a_i)$，那么，我们只会影响$d_x$和$b_{x+a_i}$，有三种情况：

$d_{x}=d_{x+a_i}=0$：这个翻转没啥用
$d_{x}=d_{x+a_i}=1$：两个都变成$0$
$d_{x}=0,d_{x+a_i}=1$：就相当于是把$x+a_i$移到了$x$

所以我们可以先预处理出每个$d_i=1$的$i$到其他$d_j=1$的$j$的距离$g_{i,j}$
然后我们就可以状压状压$dp$了
我们用$f_s$为到达状态$s$所需最少次数
我们假设$s$中为$1$的位最大是$k$（即最大的满足$i\&2^k=1$的$k$），那么$f_{s-2^j-2^k}=min\{f_{s}+g_{j,k}\}$，其中，$j$是$s$中为$1$的位，且$j\neq k$
附上代码：

#include<cstring>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,k,nd=-1,c[10010],a[110],d[30],f[1048580],g[30][30],dis[10010];
queue<int> q;
void bfs(int x)
{
    dis[x]=0,q.push(x);
    while(!q.empty()){
        x=q.front(),q.pop();
        for(int i=1;i<=m;i++){
            if(x-a[i]>=0&&dis[x]+1<dis[x-a[i]]) dis[x-a[i]]=dis[x]+1,q.push(x-a[i]);
            if(x+a[i]<=n&&dis[x]+1<dis[x+a[i]]) dis[x+a[i]]=dis[x]+1,q.push(x+a[i]);
        }
    }
}
int main()
{
//	freopen("coin.in","r",stdin);
//	freopen("coin.out","w",stdout);
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1,j;i<=k;i++) scanf("%d",&j),c[j]=1;
    for(int i=1;i<=m;i++) scanf("%d",&a[i]);
    for(int i=0;i<=n;i++) if(c[i]!=c[i+1]) d[++nd]=i;
    for(int i=0;i<=1048576;i++) f[i]=100000000;
    for(int i=0;i<=nd;i++) for(int j=0;j<=nd;j++) g[i][j]=100000000;
    for(int i=0;i<=nd;i++){
        for(int j=0;j<=n;j++) dis[j]=100000000;
        bfs(d[i]);
        for(int j=0;j<=nd;j++) g[j][i]=g[i][j]=min(g[i][j],dis[d[j]]);
    }
    f[(1<<nd+1)-1]=0;
    for(int i=(1<<nd+1)-1,k;i;i--){
        for(k=nd;k>=0;--k) if(i&(1<<k)) break;
        for(int j=0;j<=nd;j++) if((i&(1<<j))&&j!=k) f[i-(1<<j)-(1<<k)]=min(f[i-(1<<j)-(1<<k)],f[i]+g[j][k]);
    }
    if(f[0]<100000000) printf("%d",f[0]);
    else printf("-1");
}