传送门
可将题目从后往前做
则问题变为将 01 序列转化为全是 0 的序列
由于对于当前序列不好操作
将当前序列差分
0 表示与前一位相同,1 表示与前一位不同
差分序列至多有 20 个 1
操作变为反转两个之间距离为 a[i]的数
易证选两个 0 反转的操作是无意义的
而选一个 1 和一个 0 反转相当于将 1 左移或右移 a[i]
当可以反转两个 1 时即消灭了两个 1
最终任务变为求消灭所有 1 的最小操作次数
可以 bfs 预处理消灭每两个 1 的最小代价
然后状压 dp,msk 表示没被消灭的 1 的序号
dp[msk]表示消灭这 msk 的最小代价
可枚举任意两个 1 消除来转移
程序:
//by xxj
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ll long long
#define pii pair<int,int>
#define lowbit(x) x&-x
using namespace std;
const int inf=1e9+7;
const double eps=1e-10;
const ll linf=1e18+7;
const ll hh=523;
//const int mod=;
int n,k,l;
int x[17],a[107],cf[27],cnt=0;
int visited[10007];
int xx[10007];
int q[10007];
int wxt[27][27];
int dp[(1<<20)];
int go(int msk){
if (dp[msk]!=-1){
return dp[msk];
}
if (msk==0){
return 0;
}
vector<int> v;
for (int i=1;i<=cnt;i++){
if (msk & (1<<(i-1))){
v.push_back(i-1);
}
}
dp[msk]=inf;
for (int i=1;i<v.size();i++){
if (wxt[v[0]+1][v[i]+1]==-1){
continue;
}
dp[msk]=min(dp[msk],go(msk-(1<<v[0])-(1<<v[i]))+wxt[v[0]+1][v[i]+1]);
}
return dp[msk];
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d%d",&n,&k,&l);
for (int i=0;i<k;i++){
scanf("%d",x+i);
xx[x[i]-1]=(xx[x[i]-1]+1)%2;
xx[x[i]]=(xx[x[i]]+1)%2;
}
for (int i=0;i<=n;i++){
if (xx[i]==1){
cnt++;
cf[cnt]=i;
xx[i]=cnt;
}
}
for (int i=0;i<l;i++){
scanf("%d",a+i);
}
for (int i=1;i<=cnt;i++){
for (int j=1;j<=cnt;j++){
wxt[i][j]=-1;
}
}
for (int i=1;i<=cnt;i++){
memset(visited,0,sizeof(visited));
visited[cf[i]]=1;
wxt[i][i]=0;
int op=0,ed=0;
q[0]=cf[i];
while (op<=ed){
int t=q[op];
op++;
for (int j=0;j<l;j++){
if (t+a[j]<=n && !visited[t+a[j]]){
if (xx[t+a[j]]){
wxt[i][xx[t+a[j]]]=visited[t];
}
visited[t+a[j]]=visited[t]+1;
ed++;
q[ed]=(t+a[j]);
}
if (t-a[j]>=0 && !visited[t-a[j]]){
if (xx[t-a[j]]){
wxt[i][xx[t-a[j]]]=visited[t];
}
visited[t-a[j]]=visited[t]+1;
ed++;
q[ed]=(t-a[j]);
}
}
}
}
memset(dp,-1,sizeof(dp));
int ans=go((1<<cnt)-1);
if (ans>=inf){
puts("-1");
return 0;
}
printf("%d\n",ans);
return 0;
}
/*
input:
*/
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于