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

2/12 状压dp枚举子集类问题练习

[POI 2004] PRZ

预处理出每个状态需要的时间和重量,然后就是板子。

AT_dp_u Grouping

dp[mask] 表示当前已选兔子的情况为 mask 的最大总分值。(其中,mask 为二进制状压变量,每个二进制位对应一个兔子的占用情况)

\(dp[mask]=max\{dp[t]+v[t\oplus mask]\}\)

其中,t 是 mask 的子集。

P2167 [SDOI2009] Bill的挑战

设 dp[i][mask] 表示当前构造到了第 i 位,当前依然“匹配”的字符串集合为 mask 的方案数。

定义 f[i][ch] 表示在第 i 位填入字符 ch ('a'-'z') 时,有哪些字符串能匹配。用二进制状态表示。

转移方程:\(dp[i+1,mask\ \&\ f[i+1,ch]]=\sum dp[i,mask];\)

其中 ch 为枚举的字母。

详细思路记得看课件。

P3694 邦邦的大合唱站队

dp[i]表示i状态下最小的出列(不一致)的个数。

比如 dp[1101] 表示从头到位为 1/3/4 乐队的偶像的最小出列个数。

\[dp[i] = \min\bigl(dp[i \ \oplus \ 2^j] + num[j] - \bigl(\text{sum}[\text{len}[j]] - \text{sum}[\text{len} - num[j]][j]\bigr)\bigr) \]

j 表示团队编号,sum 表示某种团队的前缀和,len 表示到此已经排到的长度。

http://www.jsqmd.com/news/375281/

相关文章:

  • Vim命令
  • 如何解决 Vue 项目启动时出现的 “No such module: http_parser” 错误问题:从0到1避坑指南(附完整代码)
  • 《计算机是怎样跑起来的》——让程序像流水一样流动
  • 2026板材工厂排行榜 - 品牌推荐(官方)
  • 大数据诊断性分析:从数据采集到结果可视化的全流程
  • 2026 年四川优质仿真恐龙厂家推荐榜:以科技赋能文旅,凭实力领跑仿真恐龙场景体验 - 深度智识库
  • 从高低压开关柜到箱式变电站——2026中国电力工程五大优质厂家推荐 - 深度智识库
  • PromQL
  • 深入解析:基于 Spring Boot 的医院预约挂号系统(全端协同)设计与实现
  • 第1章 程序点滴-1.2 高手是怎样练成的(3)
  • 基于深度学习YOLOv10的热成像人员检测系统(YOLOv10+YOLO数据集+UI界面+Python项目源码+模型)
  • 第1章 程序点滴-1.3 正确的入门方法(1)
  • 基于深度学习YOLOv10的麻将识别检测系统(YOLOv10+YOLO数据集+UI界面+Python项目源码+模型)
  • AI工具免费模型排名对比 (2026-02-12)
  • 果乐士米糊:跳出“水+谷物”框架,重新定义宝宝主食辅食新标准 - 速递信息
  • 行业内专业的2026板材十大品牌排名 - 品牌推荐(官方)
  • 基于深度学习YOLOv8的扑克牌识别检测系统(YOLOv8+YOLO数据集+UI界面+Python项目源码+模型)
  • 基于.NET Core MVC和SQL Server的在线考试系统源码包:国际化管理、多角色操...
  • 2026年企业网盘选型盘点:坚果云领衔8款主流产品实力对比
  • 构建之法(3)
  • 2026年企业级共享网盘深度盘点:15款主流产品选型指南
  • AI驱动的敏捷团队技能组:让Claude变身完整开发团队【Scrum-Skills】
  • No152:AI中国故事-对话祖冲之——圆周率与AI精度:数学直觉与极限探索
  • 哪些国产网盘适合企业私有部署场景
  • 有实力的2025板材工厂排名 - 品牌推荐(官方)
  • 2026年机器学习论文高效阅读法
  • C++ 反射式注册表模式 (Registry Pattern) 笔记
  • 解决leetcode第3836题.恰好k个下标对的最大得分
  • 深入解析:数据结构:初识“树”
  • 2026 最新仿真动物、仿真恐龙厂商推荐 TOP5 排行榜单,已权威测评 - 深度智识库