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

已严肃完成今日96种状态的超级神仙DP大学习

传送门

官方题解做法。

注:因为黑格子上只能放黑棋,白格子上只能放白棋,所以有的时候没必要区分是格子还是棋

Step 1 - 找性质

  • 对于一个极大棋子联通块,我们可以在它左边或者右边放一个棋子(具体来讲选择对应位置格子颜色的棋子然后放上一个相同颜色的棋子)

这意味着,我们对于我们可能的一个方案,我们只需要在可能的方案中的每个联通块中生成一个小段(我们称之为标记)然后就可以用这个小段来“长”出目标方案。

  • 我们如果要新放一个标记,那必须满足当前所有与已放棋子相邻的格子(称作缺口)一定得是同一个颜色的(这样才能选择另一个颜色来做标记)

于是我们可以分类,将一个所有相邻格子都是白的情况下放的标记,称作白放置,否则称作黑放置。

  • 在一个可能的最优方案中,只可能出现一种颜色的放置,即不会黑白放置都出现。

    证明:不妨设先进行了一次白放置,后进行了一次黑放置。对于第二次黑放置,它要求所有段的缺口都是黑的,而第一次白放置要求所有段的缺口都是白的。所以在两次放置之间必须把所有白缺口的段都长成黑缺口。但段的生长本身不依赖其他段,所以你大可以在第一次就把所有白缺口长成黑缺口,然后把第一次变成白放置。

于是我们可以直接枚举答案是黑放置还是白放置,然后对两种情况取 min 即可。

不妨设答案是白放置。

  • 白放置一定只能放黑棋子。然后我们又要求所有缺口都是白的,因此大部分情况下标记都是一个极大的黑联通块。

但第一次和最后一次的约束不太一样,具体的:

  • 第一次因为是随便放,因此可以放一个白的单点,满足两边的缺口都是白的就行。

  • 最后一次因为不用后面的生长,因此可以只放一个黑的单点。

Step 2 - DP

OK,我们已经找到了方案的组成部分,具体的有三种:

  • 左右都是白的白点,称作 a1。
  • 极大黑联通块,称作 a2。
  • 黑点,称作 a3。

我们要求方案中的每个联通块都包含一个 a1,a2 或 a3。且 a1 和 a3 只能出现一次。

设计状态:f[i][0/1][0/1][0/1][0/1][0/1/2][0/1]

表示:当前位置,用了 a1 吗?用了 a3 吗?当前格子选了吗?当前的联通块里有 a1 吗?当前的联通块里没开始 a2(0),当前联通块里开始了但没结束 a2(1),当前联通块结束了 a2(2)。当前联通块里有 a3 吗?

这是一个高达 96 种状态的 DP,不可能去手动转移。我们考虑给转移归类。

我们可以拆成两步:第一步先处理当前的这个点的状态,要不要放进 a1/a2/a3?第二步再直接转移到下一个点。

详细的可以看代码,写了注释。

Link

http://www.hskmm.com/?act=detail&tid=27575

相关文章:

  • P3388 【模板】割点(割顶) tarjan
  • new day
  • 10.9每日总结
  • vLLM 吞吐量优化实战:10个KV-Cache调优方法让tokens/sec翻倍
  • Linux之周期性定时任务实践
  • MyBatis-Plus 的 QueryWrapper 应用以及在内存中处理JSON数组字符串匹配
  • P9461 「EZEC-14」众数 II
  • 提升
  • 详细介绍:win11 安装 WSL2 Ubuntu 并支持远程 SSH 登录
  • Ai元人文:论智能的“全息定帧”与“渐进式显影”机制
  • 24 LCA模拟赛2T4 colorful 题解
  • 23 LCA模拟赛2T2 异或排列 题解
  • Bugkuctf的哥哥的秘密
  • 国庆做题记录(基础算法)
  • fp16训练神经网络时出现nan问题
  • 第十篇
  • 504 品酒大会!!!!!!
  • 整体理解pai0-具身智能-01 - jack
  • 【数据结构】可撤销并查集 - Slayer
  • 皮卡鱼源码导读
  • 高斯消元学习笔记
  • newDay07
  • 10月9日
  • 从开放重定向到XSS:漏洞升级实战
  • 余弦日记
  • 【题解】P11459 [USACO24DEC] Its Mooin Time P
  • 创建一个springboot项目,mybatis连接嵌入式数据库H2,实现增删改查功能
  • 基于众包的产品质量比较与推荐算法研究
  • 10/9
  • 2025.10.9