Password

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

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

相关帖子

回帖

欢迎来到这里!

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

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

推荐标签 标签

  • Rust

    Rust 是一门赋予每个人构建可靠且高效软件能力的语言。Rust 由 Mozilla 开发,最早发布于 2014 年 9 月。

    58 引用 • 22 回帖
  • Spring

    Spring 是一个开源框架,是于 2003 年兴起的一个轻量级的 Java 开发框架,由 Rod Johnson 在其著作《Expert One-On-One J2EE Development and Design》中阐述的部分理念和原型衍生而来。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构,分层架构允许使用者选择使用哪一个组件,同时为 JavaEE 应用程序开发提供集成的框架。

    944 引用 • 1459 回帖 • 17 关注
  • JRebel

    JRebel 是一款 Java 虚拟机插件,它使得 Java 程序员能在不进行重部署的情况下,即时看到代码的改变对一个应用程序带来的影响。

    26 引用 • 78 回帖 • 664 关注
  • SendCloud

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

    2 引用 • 8 回帖 • 483 关注
  • 代码片段

    代码片段分为 CSS 与 JS 两种代码,添加在 [设置 - 外观 - 代码片段] 中,这些代码会在思源笔记加载时自动执行,用于改善笔记的样式或功能。

    用户在该标签下分享代码片段时需在帖子标题前添加 [css] [js] 用于区分代码片段类型。

    69 引用 • 372 回帖
  • Android

    Android 是一种以 Linux 为基础的开放源码操作系统,主要使用于便携设备。2005 年由 Google 收购注资,并拉拢多家制造商组成开放手机联盟开发改良,逐渐扩展到到平板电脑及其他领域上。

    334 引用 • 323 回帖 • 1 关注
  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations,简称 DJI),成立于 2006 年,是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商,客户遍布全球 100 多个国家。通过持续的创新,大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖
  • RabbitMQ

    RabbitMQ 是一个开源的 AMQP 实现,服务器端用 Erlang 语言编写,支持多种语言客户端,如:Python、Ruby、.NET、Java、C、PHP、ActionScript 等。用于在分布式系统中存储转发消息,在易用性、扩展性、高可用性等方面表现不俗。

    49 引用 • 60 回帖 • 362 关注
  • Logseq

    Logseq 是一个隐私优先、开源的知识库工具。

    Logseq is a joyful, open-source outliner that works on top of local plain-text Markdown and Org-mode files. Use it to write, organize and share your thoughts, keep your to-do list, and build your own digital garden.

    6 引用 • 63 回帖
  • Elasticsearch

    Elasticsearch 是一个基于 Lucene 的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于 RESTful 接口。Elasticsearch 是用 Java 开发的,并作为 Apache 许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。

    117 引用 • 99 回帖 • 212 关注
  • 招聘

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

    190 引用 • 1057 回帖
  • Maven

    Maven 是基于项目对象模型(POM)、通过一小段描述信息来管理项目的构建、报告和文档的软件项目管理工具。

    186 引用 • 318 回帖 • 302 关注
  • 百度

    百度(Nasdaq:BIDU)是全球最大的中文搜索引擎、最大的中文网站。2000 年 1 月由李彦宏创立于北京中关村,致力于向人们提供“简单,可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”,象征着百度对中文信息检索技术的执著追求。

    63 引用 • 785 回帖 • 175 关注
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    6 引用 • 14 回帖 • 2 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    311 引用 • 546 回帖
  • Q&A

    提问之前请先看《提问的智慧》,好的问题比好的答案更有价值。

    8112 引用 • 37001 回帖 • 160 关注
  • SEO

    发布对别人有帮助的原创内容是最好的 SEO 方式。

    35 引用 • 200 回帖 • 22 关注
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 680 关注
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 587 关注
  • danl
    132 关注
  • Gitea

    Gitea 是一个开源社区驱动的轻量级代码托管解决方案,后端采用 Go 编写,采用 MIT 许可证。

    4 引用 • 16 回帖 • 5 关注
  • 服务器

    服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。

    125 引用 • 588 回帖
  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务,可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务,所以该项目也已经停止维护了!

    34 引用 • 467 回帖 • 742 关注
  • 以太坊

    以太坊(Ethereum)并不是一个机构,而是一款能够在区块链上实现智能合约、开源的底层系统。以太坊是一个平台和一种编程语言 Solidity,使开发人员能够建立和发布下一代去中心化应用。 以太坊可以用来编程、分散、担保和交易任何事物:投票、域名、金融交易所、众筹、公司管理、合同和知识产权等等。

    34 引用 • 367 回帖
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 19 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3187 引用 • 8213 回帖
  • 倾城之链
    23 引用 • 66 回帖 • 136 关注