[日常训练]翻转硬币

Description

$n$枚硬币正面朝上摆成一排,给定$a[1],a[2],…,a[m]$,每次操作可以翻转连续$a[i]$个硬币.要求经过最少次数的操作,使得仅第$x[1],x[2],…,x[k]$枚硬币反面朝上,输出最少次数.

Input

第一行三个整数$n,k,m$.

第二行$k$个整数表示需要反面朝上的硬币位置，从$1$编号.

第三行$m$个整数表示$a[1],a[2],…,a[m]$.

Output

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

Sample Input

10 8 2

1 2 3 5 6 7 8 9

3 5

Sample Output

HINT

$1;leq;n;leq;10^4,1;leq;k;leq;10,1;leq;m;leq;100,1;leq;a[i];leq;n$.

Solution

因为每次翻转改变的是相邻两个硬币之间的相对状态.

所以用$b[i]$表示相邻两个硬币之间的相对状态($0$:状态相同;$1$状态不同).

初始状态和终止状态便可知了,现在要将终止状态还原回初始状态.

每当翻转$[x+1,x+a[i]]$(长度为$a[i]$)时,只对$b[x],b[x+a[i]]$产生影响.

当$b[x]=b[x+a[i]]=0$时,操作劣.

当$b[x]=b[x+a[i]]=1$时,可消掉两个元素.

当$b[x]=0,b[x+a[i]]=1$时,相当于$x+a[i]$移动到$x$.

所以先预处理出每个$b[i]=1$的$i$到其他$b[j]=1$的$j$的距离$g[i][j]$,状压$dp$即可.

$f[i]$为到达状态$i$(二进制表状态)所需最少步数.

因为每个元素早消晚消都得消,而且顺序没影响,

所以设$k$为使得$i&(1$<<$k)=1$最大的$k$,

则$f[i-(1$<<$j)-(1$<<$k)]=min(f[i]+g[j][k])(i&(1$<<$j)=1,j; ot=;k)$.

#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define K 25
#define M 105
#define N 10005
#define F 1048576
#define INF 20000000
using namespace std;
typedef long long ll;
int g[K][K],f[F],a[M],p[K],dis[N],n,m,k,cnt=-1;
bool b[N];
queue<int> q;
inline void bfs(int u){
    dis[u]=0;q.push(u);
    while(!q.empty()){
        u=q.front();q.pop();
        for(int i=1;i<=m;++i){
            if(u-a[i]>=0&&dis[u]+1<dis[u-a[i]]){
                dis[u-a[i]]=dis[u]+1;q.push(u-a[i]);
            }
            if(u+a[i]<=n&&dis[u]+1<dis[u+a[i]]){
                dis[u+a[i]]=dis[u]+1;q.push(u+a[i]);
            }
        }
    }
}
inline void Aireen(){
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1,j;i<=k;++i){
        scanf("%d",&j);b[j]=true;
    }
    for(int i=1;i<=m;++i)
        scanf("%d",&a[i]);
    for(int i=0;i<=n;++i)
        if(b[i]!=b[i+1])
            p[++cnt]=i;
    for(int i=0;i<F;++i)
        f[i]=INF;
    for(int i=0;i<=cnt;++i)
        for(int j=i+1;j<=cnt;++j)
            g[i][j]=g[j][i]=INF;
    for(int i=0;i<=cnt;++i){
        for(int j=0;j<=n;++j)
            dis[j]=INF;
        bfs(p[i]);
        for(int j=0;j<=cnt;++j)
            g[j][i]=g[i][j]=min(g[i][j],dis[p[j]]);
    }
    f[(1<<cnt+1)-1]=0;
    for(int i=(1<<cnt+1)-1,k;i;--i){
        for(k=cnt;k>=0;--k)
            if(i&(1<<k)) break;
        for(int j=0;j<=cnt;++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]<INF) printf("%d
",f[0]);
    else puts("-1");
}
int main(){
    freopen("coin.in","r",stdin);
    freopen("coin.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}