计数类 DP

xishanmeigao / 2024-11-21 / 原文

P9522 [JOISC2022] 错误拼写

牛魔计数题使我旋转。

主要说一下分析思路：

根据字典序的比较方式我们可以转化一下 $T_{A_j}<T_{B_j}$ 这个条件。我们现在只考虑严格小于的情况。

字典序暗示我们要从后往前 DP，于是设 $f_{i,j}$ 表示 $s_i=j$ 的方案数。然后考虑从 $f_{i',j'}$ 转移过来，思考转移的约束。

这个约束就是对于一段 $[A,B]$ 里面的 $i'$，对 $i<A$ 都要少掉一段贡献，这段贡献和 $j$ 有关。

于是设 $h_j$ 表示 $i+1\sim n$ 中 $f_{*,j}$ 的贡献。每次移动 $i$ 的时候更新 $h_j$。用链表维护，时间复杂度 $\mathcal{O}(n|\sum|)$。

计数题好难。

P2051 [AHOI2009] 中国象棋

即每一行、每一列最多有两个棋子。

在转移的时候，我们需要依赖于上一层的状态，但往往我们无需清楚每个地方的状态具体是啥，只需知道某种状态的个数，然后使用排列组合计算。

设 $f_{i,j,k}$ 表示前 $i$ 行，有 $j$ 列一个炮，有 $k$ 列两个炮。

枚举这一行放几个炮直接转移就行。

P3158 [CQOI2011] 放棋子

发现维护个数比较困难。

发现每种颜色都是相互独立的，区域的划分依据是完整的行和列。所以可以考虑设 $f_{k,i,j}$ 表示前 $k$ 种颜色占据了 $i$ 行 $j$ 列的方案（这类题通常都可这样设），转移需要一个 $g_{i,j,k}$ 表示用 $k$ 枚同色棋子占据 $i$ 行 $j$ 列的方案。

$g$ 需要容斥。

P10982 Connected Graph

正难则反，我们求 $n$ 个点的无向不联通图个数。

一开始为了不计算重复，我设了 $f_{i,j}$ 表示 $i$ 个点，形成 $j$ 个联通块的方案，然后再它做容斥，但总有点问题。

一种可行的方法是：钦定一个点作为划分依据。

比如以 $1$ 号点为依据，设 $f_i$ 表示 $i$ 个点的联通图方案，转移时考虑 $1$ 号点所在联通块大小，让其余的点不与该联通块连边即可。

CF1989E Distance to Different

观察到 $b$ 取决于 $a$ 中相同数组成的连续段。

设 $f_{i,j}$ 表示前 $i$ 个数分成了 $j$ 个连续段的大小，转移不表，注意要特殊处理 $f_{i-2,j-1}$。

我想到这后还一直在想怎么保证每种数都填进去了这 $j$ 个段，后来才发现只需保证分成了至少 $k$ 个段就行了，具体怎么填根本不重要，因为对应的 $b$ 都是一样的。

所以第二维只用开到 $k+1$，前缀和优化。

自己实在太唐了。

CF1585F Non-equal Neighbours

感觉要记录 $i$ 选的数和 $a_i$ 的大小关系。然后可能可以转移？？貌似没人这样做。

考虑容斥，钦定有 $k$ 个 $i$ 满足 $b_i=b_{i+1}$，则 $ans=\sum\limits_{k=0}^{n-1}(-1)^kF(k)$。

于是有一个朴素的 DP，设 $f_{i,j}$ 表示前 $i$ 个数，分成了 $j$ 段的方案数，时间复杂度 $\mathcal{O}(n^3)$。

然后发现我们需要的是段数的奇偶性，于是将状态改为 $f_{i,0/1}$，时间复杂度 $\mathcal{O}(n^2)$。

发现转移式里不好优化的是一个 $\min$，这个可以搞一个单调栈，然后加上一堆判断搞定。

CF1909F Small Permutation Problem

很厉害的题。

先考虑 Easy Version。一开始编了一个 DP 做法，但好像不太对。

第一步转化就是将 $(i,p_i)$ 放到坐标系上，将问题转化成放车问题，合法的放置要求每一行每一列都只有一个车。那么 $a_i-a_{i-1}$ 就对应着一个 L 字形里的点对数量。实时维护 $(1,1)\sim(i,i)$ 还未放置的行列数量即可。

考虑 Hard Version，我们可以将一段 $-1$ 缩起来，设区间 $(i,j)$ 之间全是 $-1$，那么相当于在一个 $y\times y$ 的网格挖掉左下角 $x\times x$ 的网格后形成的 L 字形网格中放 $t$ 个车，其中 $x=j-a_j$，$y=i-a_j$，$t=a_i-a_j$。这个东西可以容斥。时间复杂度 $\mathcal{O}(n)$。

[ARC180C] Subsequence and Prefix Sum

发现 $0$ 有很大的影响。发现第一个选的数也有很大影响（但这种可以归类为前面那种，因为初始值为 $0$）。

一旦前缀和出现了 $0$，后面如果只选一个数，那么跟不选没区别。如果选不止一个数，那么第一个数要是相同的选哪个都一样。怎么办？

一开始想用最小表示法，但不会。

发现自己智力不够，思维混乱，我们只需再记录 $g_i$ 表示前面和为 $i$ 且上一次为 $0$ 的方案数。然后我们不用 $f_{i-1,0}$ 转移到 $f_{i,a_i}$，这样就避免了选一个数的情况。然后用 $g_j\to f_{i,j+a_i}$，就计算上了不止选一个数的情况。每次循环后，$g_{a_i}\leftarrow g_0$，$g_0\leftarrow f_{i,0}$。

反思：思维混乱，在计数题中是大忌。要学会归纳各种情况，减少复杂的分类讨论，规约为简单的问题。