Password

本贴最后更新于 2128 天前,其中的信息可能已经时移俗易

传送门
可将题目从后往前做
则问题变为将 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:
*/

相关帖子

回帖

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • V2EX

    V2EX 是创意工作者们的社区。这里目前汇聚了超过 400,000 名主要来自互联网行业、游戏行业和媒体行业的创意工作者。V2EX 希望能够成为创意工作者们的生活和事业的一部分。

    17 引用 • 236 回帖 • 335 关注
  • CodeMirror
    1 引用 • 2 回帖 • 126 关注
  • Ruby

    Ruby 是一种开源的面向对象程序设计的服务器端脚本语言,在 20 世纪 90 年代中期由日本的松本行弘(まつもとゆきひろ/Yukihiro Matsumoto)设计并开发。在 Ruby 社区,松本也被称为马茨(Matz)。

    7 引用 • 31 回帖 • 212 关注
  • DNSPod

    DNSPod 建立于 2006 年 3 月份,是一款免费智能 DNS 产品。 DNSPod 可以为同时有电信、网通、教育网服务器的网站提供智能的解析,让电信用户访问电信的服务器,网通的用户访问网通的服务器,教育网的用户访问教育网的服务器,达到互联互通的效果。

    6 引用 • 26 回帖 • 505 关注
  • SendCloud

    SendCloud 由搜狐武汉研发中心孵化的项目,是致力于为开发者提供高质量的触发邮件服务的云端邮件发送平台,为开发者提供便利的 API 接口来调用服务,让邮件准确迅速到达用户收件箱并获得强大的追踪数据。

    2 引用 • 8 回帖 • 478 关注
  • 星云链

    星云链是一个开源公链,业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎,一个公链的所有功能,它基本都有,比如你可以用它来开发部署你的去中心化的 APP,你可以在上面编写智能合约,发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖 • 2 关注
  • 阿里云

    阿里云是阿里巴巴集团旗下公司,是全球领先的云计算及人工智能科技公司。提供云服务器、云数据库、云安全等云计算服务,以及大数据、人工智能服务、精准定制基于场景的行业解决方案。

    89 引用 • 345 回帖
  • NetBeans

    NetBeans 是一个始于 1997 年的 Xelfi 计划,本身是捷克布拉格查理大学的数学及物理学院的学生计划。此计划延伸而成立了一家公司进而发展这个商用版本的 NetBeans IDE,直到 1999 年 Sun 买下此公司。Sun 于次年(2000 年)六月将 NetBeans IDE 开源,直到现在 NetBeans 的社群依然持续增长。

    78 引用 • 102 回帖 • 672 关注
  • gRpc
    11 引用 • 9 回帖 • 60 关注
  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    21 引用 • 245 回帖 • 248 关注
  • 深度学习

    深度学习(Deep Learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。

    52 引用 • 40 回帖
  • Love2D

    Love2D 是一个开源的, 跨平台的 2D 游戏引擎。使用纯 Lua 脚本来进行游戏开发。目前支持的平台有 Windows, Mac OS X, Linux, Android 和 iOS。

    14 引用 • 53 回帖 • 527 关注
  • GAE

    Google App Engine(GAE)是 Google 管理的数据中心中用于 WEB 应用程序的开发和托管的平台。2008 年 4 月 发布第一个测试版本。目前支持 Python、Java 和 Go 开发部署。全球已有数十万的开发者在其上开发了众多的应用。

    14 引用 • 42 回帖 • 754 关注
  • Scala

    Scala 是一门多范式的编程语言,集成面向对象编程和函数式编程的各种特性。

    13 引用 • 11 回帖 • 123 关注
  • ZooKeeper

    ZooKeeper 是一个分布式的,开放源码的分布式应用程序协调服务,是 Google 的 Chubby 一个开源的实现,是 Hadoop 和 HBase 的重要组件。它是一个为分布式应用提供一致性服务的软件,提供的功能包括:配置维护、域名服务、分布式同步、组服务等。

    59 引用 • 29 回帖 • 3 关注
  • Vditor

    Vditor 是一款浏览器端的 Markdown 编辑器,支持所见即所得、即时渲染(类似 Typora)和分屏预览模式。它使用 TypeScript 实现,支持原生 JavaScript、Vue、React 和 Angular。

    346 引用 • 1801 回帖 • 3 关注
  • 书籍

    宋真宗赵恒曾经说过:“书中自有黄金屋,书中自有颜如玉。”

    77 引用 • 390 回帖
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 2 关注
  • 一些有用的避坑指南。

    69 引用 • 93 回帖
  • 脑图

    脑图又叫思维导图,是表达发散性思维的有效图形思维工具 ,它简单却又很有效,是一种实用性的思维工具。

    25 引用 • 83 回帖
  • BAE

    百度应用引擎(Baidu App Engine)提供了 PHP、Java、Python 的执行环境,以及云存储、消息服务、云数据库等全面的云服务。它可以让开发者实现自动地部署和管理应用,并且提供动态扩容和负载均衡的运行环境,让开发者不用考虑高成本的运维工作,只需专注于业务逻辑,大大降低了开发者学习和迁移的成本。

    19 引用 • 75 回帖 • 631 关注
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 625 关注
  • Hexo

    Hexo 是一款快速、简洁且高效的博客框架,使用 Node.js 编写。

    21 引用 • 140 回帖 • 3 关注
  • 创造

    你创造的作品可能会帮助到很多人,如果是开源项目的话就更赞了!

    176 引用 • 995 回帖 • 1 关注
  • Laravel

    Laravel 是一套简洁、优雅的 PHP Web 开发框架。它采用 MVC 设计,是一款崇尚开发效率的全栈框架。

    20 引用 • 23 回帖 • 725 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    190 引用 • 1057 回帖 • 1 关注
  • Gzip

    gzip (GNU zip)是 GNU 自由软件的文件压缩程序。我们在 Linux 中经常会用到后缀为 .gz 的文件,它们就是 Gzip 格式的。现今已经成为互联网上使用非常普遍的一种数据压缩格式,或者说一种文件格式。

    9 引用 • 12 回帖 • 136 关注