Minimax

DP 线段树合并 动态 DP

有两个思路。

算法一

枚举，设表示结点的权值大于等于的概率。可以树形 DP。设是的两个儿子：

如果是叶子结点，那么。

由于会变化，因此是个动态 DP。

由于需要树链剖分和线段树维护区间矩阵乘法，复杂度是的，是常数。

算法二

设表示的权值为的概率。由于互不相同，则和不可能同时大于。不妨设，那么

在线段树合并的过程中维护括号里的和即可。类似缺一背包。

时间复杂度。

代码

Slay the Spire

DP 计数

用，分别表示强化牌和攻击牌。

我们肯定会先打出所有的强化牌再打攻击牌。

把一张攻击牌换成强化牌不会使总伤害变小。

因此我们枚举随机的张牌中有张强化牌，然后分类讨论：

  • 若，那么强化牌全选，剩下的张攻击牌里选出张最大的。
  • 若，那么强化牌里选张最大的，然后攻击牌里选一张最大的。

考虑强化牌部分的系数。

将强化牌从大到小排序。我们设表示前张强化牌里选张的乘积的和。则。

第一种情况可以直接用表示。第二种情况可以转化为：选张强化牌，计算其中的前大的乘积的和，可以枚举第大的牌是什么，得到。

考虑攻击牌部分的系数。

将攻击牌从小到大排序。对于第一种情况，设表示前张攻击牌里选出张，这张中前大的数之和的和。那么「张攻击牌里选出张最大的」可以表示为。转移如下：

你发现第三维可以扔掉。这样就是个二维 DP 了。

第二种情况比较 trivial，就不展开了。

总时间复杂度。

代码

随机算法

DP 独立集

设表示的邻居集合（包括它自己）。

看到本题容易联想到朴素的最大独立集 DP：设表示的最大独立集。而这个 DP 有个缺陷：它考虑不到那些不在独立集中的点。如果要拓展这个思路，就需要额外加一个状态表示当前还有哪些点没有被放入排列。

换个思路。

我们发现。因此我们可以把目前已被覆盖的点计入状态，然后在转移的过程中处理放入排列的贡献。

换言之，设表示当前放入排列的数的集合是，且的独立集大小为的方案数。转移时枚举，然后把里的点放入排列，计算系数即可：

设是的最大独立集大小，那么 答案就是。

时间复杂度，据说卡常能过。

设表示覆盖的最大独立集大小（注意不是的最大独立集，指的是的最大的），答案亦可写成。

容易发现只会由转移而来（最优子结构）。也就是说我去掉覆盖的最大独立集中的一个点以及只被它覆盖的点得到和独立集，那么仍是的最大独立集。

因此的第一维就不需要了，用辅助转移即可。

时间复杂度。

代码