UVA e 11795 洛克人的难题

news/2024/10/17 20:32:59/

题目大意
洛克人有一个武器,它需要按照一定的顺序消灭n个其他的机器人,每消灭一个机器人将会得到他的武器,而且某些机器人只能用特定的武器才能将其消灭。统计出可以消灭所有机器人的顺序总数.
分析
由于题目中给定的n值很小可以采用状压Dp,用二进制的每一个位来表示每一个机器人
我们可以构成一个集合q表示消灭i后,获得武器可以消灭的敌人q(i);

		for (int i = 0; i <=n; i++) {cin >> ch;for (int j = 0; ch[j]!='\0'; j++){val = ch[j] - '0';if (val)  q[i] |= (1 <<j);}}

我们用数组state保存消灭若干个机器人后可以消灭的敌人,只需要枚举结合就可
初始状态设为去q[0]表示洛克人的武器起初就有

			for (int s = 0; s < (1 << n); s++) {state[s] = q[0];for (int j = 0; j < n; j++)if ((1 << j)&s)    state[s] |= q[j+1];	;}	

最后通过在集合的帮助下就可以就算顺序了

		d[0]= 1;for (int s = 1; s < (1 << n); s++) {d[s] = 0;for (int j = 0; j < n; j++) {if (((1<<j)&s) && (state[s ^ (1 << j)] & (1 << j)))d[s] += d[s ^ (1 << j)];}}

http://www.ppmy.cn/news/573023.html

相关文章

洛克人java下载_JAVA 1.7并发之LinkedTransferQueue原理理解

昨天刚看完BlockingQueue觉得好高级啊&#xff0c;今天扫到1.7就发现了升级版。。。。 就是作者的论文啦&#xff0c;纯英文。。。比较难啃&#xff0c;但是我觉得逻辑上比看代码容易理解&#xff0c;其实代码什么u啊h啊看得很混 LinkedTransferQueue 起源&#xff1a; 我觉得是…

洛克人html5,《洛克人Zero/Zx合集》:跳票冷饭,与预期有差但依旧很香

前言 洛克人系列&#xff0c;卡普空旗下经典IP之一&#xff0c;一直都是以高难度著称&#xff0c;相信很多90后玩家的童年都有游玩洛克人的经历。从18年发布的洛克人11&#xff0c;整个系列发展有30余年&#xff0c;洛克人元组系列、X系列的合集早已上线Steam&#xff0c;Zero/…

Python多任务执行方式

一、多任务的执行方式 并发&#xff1a;在一段时间内交替去执行任务&#xff08;单核CPU&#xff09;并行&#xff1a;CPU核数大于任务数 二、进程&#xff08;实现多任务&#xff09;——操作系统调度 进程是操作系统进行资源分配的基本单元一个程序至少有一个进程&#xf…

网关全局过滤器:Java中的强大工具

文章目录 网关过滤器简介网关过滤器的作用过滤器的生命周期实际应用示例权限过滤器解析 总结 网关过滤器简介 网关过滤器是一个位于应用程序和底层服务之间的组件&#xff0c;它截取进出网络请求&#xff0c;并提供对请求和响应进行处理的机制。它可以在请求到达目标服务之前或…

10种常用排序算法

10种常用排序算法 0——序言 以下是常用的排序算法及其对应的时间复杂度&#xff1a; 冒泡排序&#xff08;Bubble Sort&#xff09;&#xff1a; 最好情况时间复杂度&#xff1a;O(n)平均情况时间复杂度&#xff1a;O(n^2)最坏情况时间复杂度&#xff1a;O(n^2) 选择排序&a…

c++11中的多线程std::thread

c11中的多线程std::thread 在c11中提供了新的多线程的创建方式std::thread, 丰富了对于多线程的使用。 std::thread类的构造函数的格式如下所示&#xff1a; thread() noexcept; //default constructor 其中noexcept表示函数不会抛出异常&#xff0c;如果抛出异常程序…

深入探究 ReentrantLock 的应用和原理

博主介绍&#xff1a; ✌博主从事应用安全和大数据领域&#xff0c;有8年研发经验&#xff0c;5年面试官经验&#xff0c;Java技术专家✌ Java知识图谱点击链接&#xff1a;体系化学习Java&#xff08;Java面试专题&#xff09; &#x1f495;&#x1f495; 感兴趣的同学可以收…

Ajax技术的秘密揭秘:异步传输,高效交互

文章目录 I. 什么是AjaxAjax的定义和起源Ajax与传统的Web应用程序之间的区别 II. Ajax的工作原理Ajax的基本原理Ajax如何通过异步传输实现无需刷新页面 III. Ajax的应用场景在Web应用程序中应用Ajax的优势Ajax在哪些场景中使用 IV. Ajax的组成部分和APIXHR对象FormData对象Fetc…