当前位置: 首页 > news >正文

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种口味的糖果出售。 为了方便描述&#xff0c;我们将 M种口味编号 1∼M。 小明希望能品尝到所有口味的糖果。 遗憾的是老板并不单独出售糖果&#xff0c;而是 K颗一包整包出售。 幸好糖果包装上注明了其中 K颗糖果的口味&#xff0c;所以小…...

【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 开发时&#xff0c;在 C# 中通过 Renderer 取材质操作是非常常见的操作&#xff0c;Renderer 有两种常规获取材质的方式&#xff1a; sharedMaterials&#xff1a;可以理解这个就是原始材质&#xff0c;所有使…...

java学习----网络编程

网络编程入门 网络编程概述 计算机网络 ​ 计算机网络是指地理位置不同的具有独立功能的计算机及其外部设备&#xff0c;通过通信线路连接起来&#xff0c;在网络操作系统&#xff0c;网络管理软件及网络通信协议的管理协调下&#xff0c;实现资源共享和信息传递的计算机系统…...

这些「误区」99%的研发都踩过

意识不到误区的存在最为离谱&#xff1b; 01生活中&#xff0c;职场上&#xff0c;游戏里&#xff0c;都少不了正面对喷过&#xff1a;意识太差&#xff1b; 在个人的认知中意识即思维&#xff0c;意识太差即思维中存在的误区比较多&#xff1b; 每个人或多或少都存在思维上的…...

Bi系统跟数据中台的区别是什么?

随着数据时代的发展&#xff0c;BI分析是当今数据时代必不可少的能力之一。BI系统通过系统化产品化的方法&#xff0c;能够大幅降低数据的获取成本、提升数据使用效率。同时借助可视化、交互式的操作&#xff0c;可以高效支持业务的分析及发展。 BI如此火热&#xff0c;随之而…...

微信小程序反编译方法分享

文章目录一、前言二、准备工作&#xff08;一&#xff09;安装Nodejs&#xff08;二&#xff09;解密和逆向工具三、小程序缓存文件解密&#xff08;一&#xff09;定位小程序缓存路径&#xff08;二&#xff09;源码解密&#xff08;三&#xff09;源码反编译四、小结一、前言…...

有了这些接口测试用例+工具,测试效率想不提升都难

写在前面&#xff1a;在日常开发过程中&#xff0c;有人做前端开发&#xff0c;有人负责后端开发。接口的主要作用就是连接前后台。但是&#xff0c;由于前端和后端开发的速度可能不一样&#xff0c;尤其是后端开发好了&#xff0c;但前端还未开发。这种时候我们需要做接口测试…...

麒麟 arm架构安装nginx

目录 1、下载nginx安装包并解压 在线安装&#xff1a; 离线安装&#xff1a; 上传nginx安装包&#xff08;下载地址&#xff1a;https://nginx.org/download/nginx-1.20.2.tar.gz&#xff09;到指定目录 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写过笔记了&#xff0c;没想到无意间打开&#xff0c;编辑器更新啦&#xff01;以前巨难用的“富文本编辑器”终于改观了&#x1f62d;变的好像语雀&#xff0c;うれしい1. 视图/画面操作a. 画面缩放&#xff08;Zoom&#xff09;&#xff1a;F11/F12 或 鼠标滚轮b…...

cmd del命令笔记

使用 /s 删除文件夹下所有的 del /s sub # 删除目录下所有文件&#xff0c;这个目录不会删除 /p 确认提示 /q 静默模式&#xff0c;不会提示要不要删除 如过和/p同时使用&#xff0c;那么不提示 /a 根据属性删除&#xff0c;a是attribute的意思 del /a:r 01.jpg # 01.jp…...

apifox持续集成+java+企微机器人+xxljob定时推送

总览&#xff1a; apifox做接口测试后&#xff0c;把用例合并组装成测试套件&#xff0c;然后apifox-cli通过终端命令实现把套件执行后&#xff0c;输出本地文件的测试报告html或json。本地解析后拿到有用的解决通过定时执行推送到企微群里。 然后把html一起推到群里。 这个…...

盘点Linux内核网络知识100道题,这篇就够了

计算机网络模型 1、五层因特网协议栈和七层OSI&#xff08;Open System Interconnections&#xff09;参考模型分别是什么&#xff1f; 5层&#xff1a;应用层、传输层、网络层、数据链路层、物理层 7层&#xff1a;应用层、表示层、会话层、传输层、网络层、数据链路层、物理…...

数据库敏感字段脱敏

文章目录什么是脱敏脱敏后带来什么问题解决方案一解决方案二具体实施方案一方案二存量数据处理什么是脱敏 如果你有申请过一些软件资质&#xff0c;应该会被要求敏感数据进行加密&#xff0c;比如密码不能明文&#xff0c;用户的手机号&#xff0c;身份证信息&#xff0c;银行…...

skynet 游戏服务器探索(1)--熟悉skynet(网络)

因为做游戏服务器开发&#xff0c;大多数都跟脚本打交道&#xff0c;要么是lua,要么是python,要么是php,方便热更新的只有lua与php, php相关的游戏服务器开发&#xff0c;参考我另外的文章https://blog.csdn.net/guoyilongedu/article/details/121049511lua脚本相关的&#xff…...

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&#xff1a;被select管理的文件描述符的个数&#xff0c;最大描述符编号1fd_set *readfds&#xff1a;读文件描述符集合fd_se…...

rollup的基本使用 基本配置与处理各种文件

rollup rollup是一个javascript的模块化打包工具 可以帮助我们编译小的代码到一个大的负载的代码中 比如一个库或者一个应用 rollup与webpack的区别 rollup主要针对ES Module进行打包 另外webpack通常可以通过各种loader处理各种各样的文件 以及处理他们的依赖关系 rollup更多…...

ubuntu-debian系-redhat系

debian系 包类型&#xff1a;.deb包 本地安装包安装工具&#xff1a;dpkg 本地包管理命令&#xff1a;dpkg -i package 安装包 dpkg -r package 卸载包 dpkg -l package 查看已安装包 远程安装包安装工具&#xff1a;apt / apt-get 远程包管理命令&#xff1a;apt-get apt-cac…...

Altium Designer 18中原理图DRC编译和PCB DRC检查-AD DRC

一、原理图编译 原理图检查的主要内容有&#xff1a; 1、元件位号冲突。也即多个元件编号相同&#xff0c;例如两个电容在原理图中都被命名为C2&#xff0c;显然肯定是无法生成PCB的。 2、网络悬浮。也即网络标号没有附着在电气走线上&#xff0c;一般这种是人操作失误&…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...