1243. 糖果/状态压缩dp【AcWing】
1243. 糖果
糖果店的老板一共有 M种口味的糖果出售。
为了方便描述,我们将 M种口味编号 1∼M。
小明希望能品尝到所有口味的糖果。
遗憾的是老板并不单独出售糖果,而是 K颗一包整包出售。
幸好糖果包装上注明了其中 K颗糖果的口味,所以小明可以在买之前就知道每包内的糖果口味。
给定 N包糖果,请你计算小明最少买几包,就可以品尝到所有口味的糖果。
输入格式
第一行包含三个整数 N,M,K。
接下来 N行每行 K个整数 T1,T2,⋅⋅⋅,TK,代表一包糖果的口味。
输出格式
一个整数表示答案。
如果小明无法品尝所有口味,输出 −1。
数据范围
1≤N≤100,
1≤M,K≤20,
1≤Ti≤M
输入样例:
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2
输出样例:
2
状态压缩dp
状态压缩dp用位运算实现。
思路:
dp[ i ][ j ]表示前 i 袋糖果集齐 j 种糖果所需要的最少袋数。
可以选择第 i 袋或者不选择第 i 袋。
状态转移方程为:
dp[ i ][ j ]=min( dp[ i - 1 ][ j ] , dp[ i - 1 ][ j & (~ w[ i ])]+1 )
前面那个是不选择第 i 袋,比较好理解,后面那个可以举个例子
例如我们想要 j 为11011,而w[ i ]为 11100,取反后为00011,11011 & 00011 = 10000,故是从10000这个状态转移过来的。
然后要先预处理dp数组为100,dp[0]=0就可以了。
#include<bits/stdc++.h>
using namespace std;
int w[100],dp[1<<20];
int main()
{int n,m,k;cin>>n>>m>>k;int s=(1<<m)-1;for(int i=1;i<=n;i++){for(int j=1;j<=k;j++){int r;cin>>r;w[i]|=1<<r-1;}}for(int i=1;i<(1<<m);i++) dp[i]=100;dp[0]=0;for(int i=1;i<=n;i++){for(int j=(1<<m)-1;j>0;j--){dp[j]=min(dp[j],dp[j&(~w[i])]+1);}}(dp[s]==100)?(cout<<-1<<endl):(cout<<dp[s]<<endl);return 0;
}
相关文章:
1243. 糖果/状态压缩dp【AcWing】
1243. 糖果 糖果店的老板一共有 M种口味的糖果出售。 为了方便描述,我们将 M种口味编号 1∼M。 小明希望能品尝到所有口味的糖果。 遗憾的是老板并不单独出售糖果,而是 K颗一包整包出售。 幸好糖果包装上注明了其中 K颗糖果的口味,所以小…...
【Spring Cloud Alibaba】001-单体架构与微服务架构
【Spring Cloud Alibaba】001-单体架构与微服务 文章目录【Spring Cloud Alibaba】001-单体架构与微服务一、单体架构1、单体应用与单体架构2、单体应用架构图3、单体架构优缺点优点缺点二、微服务1、微服务的“定义”2、微服务的特性3、微服务架构图4、微服务的优缺点优点缺点…...
Renderer 使用材质分析:materials、sharedMaterials 及 MaterialPropertyBlock
一、materials 与 sharedMaterials 1.1 使用上的区别与差异 Unity 开发时,在 C# 中通过 Renderer 取材质操作是非常常见的操作,Renderer 有两种常规获取材质的方式: sharedMaterials:可以理解这个就是原始材质,所有使…...
java学习----网络编程
网络编程入门 网络编程概述 计算机网络 计算机网络是指地理位置不同的具有独立功能的计算机及其外部设备,通过通信线路连接起来,在网络操作系统,网络管理软件及网络通信协议的管理协调下,实现资源共享和信息传递的计算机系统…...
这些「误区」99%的研发都踩过
意识不到误区的存在最为离谱; 01生活中,职场上,游戏里,都少不了正面对喷过:意识太差; 在个人的认知中意识即思维,意识太差即思维中存在的误区比较多; 每个人或多或少都存在思维上的…...
Bi系统跟数据中台的区别是什么?
随着数据时代的发展,BI分析是当今数据时代必不可少的能力之一。BI系统通过系统化产品化的方法,能够大幅降低数据的获取成本、提升数据使用效率。同时借助可视化、交互式的操作,可以高效支持业务的分析及发展。 BI如此火热,随之而…...
微信小程序反编译方法分享
文章目录一、前言二、准备工作(一)安装Nodejs(二)解密和逆向工具三、小程序缓存文件解密(一)定位小程序缓存路径(二)源码解密(三)源码反编译四、小结一、前言…...
有了这些接口测试用例+工具,测试效率想不提升都难
写在前面:在日常开发过程中,有人做前端开发,有人负责后端开发。接口的主要作用就是连接前后台。但是,由于前端和后端开发的速度可能不一样,尤其是后端开发好了,但前端还未开发。这种时候我们需要做接口测试…...
麒麟 arm架构安装nginx
目录 1、下载nginx安装包并解压 在线安装: 离线安装: 上传nginx安装包(下载地址:https://nginx.org/download/nginx-1.20.2.tar.gz)到指定目录 2、安装系统相关依赖软件、组件包 1、上传或者下载对应的组件包 2、安…...
logrotate失效的排查---selinux开启状态拦截问题及解决方法
首先测试环境selinux 处于关闭状态 disable # getenforce disable重新开启selinux配置与生产环境一致 [rootlocal]# cat /etc/selinux/config # This file controls the state of SELinux on the system. # SELINUX can take one of these three values: # enforcing - S…...
Allegro使用总结-查看Layout基本操作:
好久没用CSDN写过笔记了,没想到无意间打开,编辑器更新啦!以前巨难用的“富文本编辑器”终于改观了😭变的好像语雀,うれしい1. 视图/画面操作a. 画面缩放(Zoom):F11/F12 或 鼠标滚轮b…...
cmd del命令笔记
使用 /s 删除文件夹下所有的 del /s sub # 删除目录下所有文件,这个目录不会删除 /p 确认提示 /q 静默模式,不会提示要不要删除 如过和/p同时使用,那么不提示 /a 根据属性删除,a是attribute的意思 del /a:r 01.jpg # 01.jp…...
apifox持续集成+java+企微机器人+xxljob定时推送
总览: apifox做接口测试后,把用例合并组装成测试套件,然后apifox-cli通过终端命令实现把套件执行后,输出本地文件的测试报告html或json。本地解析后拿到有用的解决通过定时执行推送到企微群里。 然后把html一起推到群里。 这个…...
盘点Linux内核网络知识100道题,这篇就够了
计算机网络模型 1、五层因特网协议栈和七层OSI(Open System Interconnections)参考模型分别是什么? 5层:应用层、传输层、网络层、数据链路层、物理层 7层:应用层、表示层、会话层、传输层、网络层、数据链路层、物理…...
数据库敏感字段脱敏
文章目录什么是脱敏脱敏后带来什么问题解决方案一解决方案二具体实施方案一方案二存量数据处理什么是脱敏 如果你有申请过一些软件资质,应该会被要求敏感数据进行加密,比如密码不能明文,用户的手机号,身份证信息,银行…...
skynet 游戏服务器探索(1)--熟悉skynet(网络)
因为做游戏服务器开发,大多数都跟脚本打交道,要么是lua,要么是python,要么是php,方便热更新的只有lua与php, php相关的游戏服务器开发,参考我另外的文章https://blog.csdn.net/guoyilongedu/article/details/121049511lua脚本相关的ÿ…...
select、poll、epoll
select、poll、epoll select int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); int nfds:被select管理的文件描述符的个数,最大描述符编号1fd_set *readfds:读文件描述符集合fd_se…...
rollup的基本使用 基本配置与处理各种文件
rollup rollup是一个javascript的模块化打包工具 可以帮助我们编译小的代码到一个大的负载的代码中 比如一个库或者一个应用 rollup与webpack的区别 rollup主要针对ES Module进行打包 另外webpack通常可以通过各种loader处理各种各样的文件 以及处理他们的依赖关系 rollup更多…...
ubuntu-debian系-redhat系
debian系 包类型:.deb包 本地安装包安装工具:dpkg 本地包管理命令:dpkg -i package 安装包 dpkg -r package 卸载包 dpkg -l package 查看已安装包 远程安装包安装工具:apt / apt-get 远程包管理命令:apt-get apt-cac…...
Altium Designer 18中原理图DRC编译和PCB DRC检查-AD DRC
一、原理图编译 原理图检查的主要内容有: 1、元件位号冲突。也即多个元件编号相同,例如两个电容在原理图中都被命名为C2,显然肯定是无法生成PCB的。 2、网络悬浮。也即网络标号没有附着在电气走线上,一般这种是人操作失误&…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
