[日常训练]翻转硬币

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

2

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\;\not=\;k)\).

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 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=0;--k)
            if(i&(1<