zxy思维题乱做

有很大一部分来自于 zxy，课件等，一般都是很强的 Trick。

CF1476F

考虑 DP，设$f(i)$ 表示前$i$ 个灯可以点亮的最长前缀，有转移：

• $i$ 朝右，若$f(i-1)\ge i$，则$f(i)=\max(f(i-1),i+p_i )$，若$f(i-1)<i$，则$f(i)=f(i-1)$。
• $i$ 朝左：不难发现只要将前缀覆盖到$i-p_i$ 即可就行，设$j$ 为第一个$f(j)\ge i-p_i$ 的位置，那么$[j+1,i-1]$ 的位置都可以朝右，那么$f(i)=\max\limits_{k=j+1}^{i-1}k+p_k$，可以二分$j$ 加 ST 表查出$\max [j+1,i-1]$。

反思：当我们要 DP 点覆盖的问题的时候，我们可以考虑覆盖一段前缀的形式。同时设计 DP 状态的时候一定要时刻考虑最小状态设计原则。

HDU6157 The Karting

权值是负的！不能贪心，直接 DP。

但是状态怎么设计呢？考虑记录路径，但是显然会算重一堆。我们可以只考虑断电，让后用前缀和记录回路的贡献。

用 DP 来处理端点，设$f(i,j,k)$ 表示前$i$ 个点中，选出$j$ 个端点，其中从左往右的端点比从右往左的端点多了$k$ 个（$k\ge 0$），转移考虑当前点的贡献，一共四种情况：

• 不选这个点：$f(i,j,k)\leftarrow f(i-1,j,k)$；
• 选这个点但是只经过：$f(i,j,k)\leftarrow f(i-1,j-1,k)$；
• 选了这个点从左往右的端点：$f(i,j,k)=\leftarrow f(i-1,j-1.k-1)+a_0 -2\times s_i$；
• 选了这个点从右往左的端点：$f(i,j,k)\leftarrow f(i-1,j-1,k+1) + a_0 + 2\times s_i $。

因为要走回去，那么答案就是$f(n,m,0)$，时间复杂度$O(n^3)$。

反思：对于匹配的问题，我们可以拆解贡献到匹配点，考虑到某一个匹配点时候带着贡献和需要匹配的记号转移，这样就能够保证转移的顺序性。

P6944 Gem Island

好题！

直接飞上去 DP 直接爆炸。考虑分析性质，首先这个过程过于庞大，我们可以分析末状态的性质。先看看对于一种最终状态$a_1,a_2,\dots,a_n$ 其发生的方案数，可以分为两个部分：

• 将$d$ 天分给$n$ 个人，钦定这$d$ 天是谁的手上的宝石数增加了：

$$\prod_{i=1}^n \binom{d-\sum_{j=1}^{i-1} (a_j -1)}{a_i-1}=\frac{d!}{\prod_{i=1}^n (a_i-1)!}$$

• 对于每一天，计算当钦定的人手上宝石数增加的方案数，有：

$$\prod_{i=1}^n (a_i -1)!$$

不

那么我可以直接 DP 求方案数啦，但是问题在于我怎么求方案中前$r$ 大的$a_i$ 和呢？有一种 DP 方法，叫搭楼梯的 dp 方法。

通俗易懂的，我们要用 DP 维护下面的东西：

***
******
******
********
********
********
**********
**********

设$f(i,j)$ 表示当前最高的楼梯有$i$ 列，楼梯里头 * 的总数为$j$ 的方案数，上面这个东西就是$f(3,59)$ 的一种方案。

转移很简单，考虑转移的时候在最高层加入一行，枚举这行里头有$k$ 个 *，让后从现有的$j$ 列里头选$k$ 列放到最左边，让后在这$k$ 行上面各加上一个 * 就是一种转移了。比如说上面的例子，枚举$k=2$ 的时候可以转移到$f(2,61)$，转移系数为$\binom{3}{2}$，转移后的形态可以这么表示：

**          <--- 新增的行
***
******
******
********
********
********
**********
**********

这种类似搭楼梯的逐层构造 DP，本质是对所有 “列高单调” 的状态等权枚举，将每一层的结构直接拆分贡献，凡是这类问题：

• 对象可以抽象为高度具有单调性的多列；
• 每一层的新增元素对目标量的贡献是可局部计算的（只依赖这一层的列数$k$，而不依赖更复杂的全局信息）

那么我们就可以用这种转移做前$k$ 大（或小）的期望，总和，分布等。

回到本题，我们把宝石对应成 *，让后每一列对应一个人就可以啦。计算前$k$ 大的方案也就转化为了前$k$ 列的 * 的和，由于我们每次加入一行的那些列，不难观察出一定就是前$k$ 大的列，而且一次局部贡献只加入一个 *，所以可以直接计算。具体的，我们设$g(i,j)$ 表示当前维护前$i$ 大，一共有$j$ 个宝石中所有方案数前$k$ 大的和，有转移：

$$g(i,j)=\sum_{k=i}^{\min(n,i)} (g(k,j-i) +\min(i,r) \times f(k,j-i))\times \binom{k}{i}$$

其中$r$ 就是题目中所要的前$k$ 大。

答案就是$\dfrac{\sum_{i=1}^n g(i,d)}{\sum_{i=1}^n f(i,d)}$。

反思：

对于这种多过程的题目，如果过程难以维护，我们可以考虑末状态有没有什么特殊性质。

学到了新的转移( •̀ ω •́ )y

哎我发现你过一段时间回来看这个题发现有些新的收获( •̀ ω •́ )y。

CF1442

想 DP，但是发现太难了耶。因为操作过于难了，并不是 DP 过于难了。

我们考虑如何简化这个问题，发掘以下性质。首先不难发现所有连在一起的同颜色的点可以一起删。也就是缩点。

让后怎么做？先从简单情况入手，把万能的灰点暂时禁言。让后考虑树是一条链的情况怎么做，因为没有灰点且已经缩点的情况下，这个链一定是黑白相见的，设链长为$len$，那么答案就是$\lfloor \dfrac{len}{2} \rfloor+1$，贪心策略是将出现次数较多的颜色删掉，让后剩下的连通块逐个删掉就可以了。

接着考虑树不是一条链的时候怎么做，发现上面的策略好像不太好去拓展，且有些情况下不是最优解。考虑再发掘一种策略，有一种策略：从最外层（度数为$1$）把同色点一层一层删掉，设$len$ 为直径，那么次数就是$\lfloor\dfrac{len}{2} \rfloor+1$。不难发现这个策略更优，可以用势能分析得出。

接着考虑有灰点的情况，问题可以转化为我们给每一个灰点选择一种颜色，使得再次所点后直径长度最短。这种情况需要我们进行 dp 了。设$f(u,i)$ 表示$u$ 颜色为$i$ 的最长链，$g(u,i)$ 表示$u$ 颜色为$i$，经过$u$ 的最长路径，转移的时候把子树$v$ 合并上来：

$$g(u,i)\leftarrow\max\{ g(u,i),\min(f(u,i)+f(v,j)+(i\neq j)) \}$$

$$f(u,i)\leftarrow \max \{ f(u,i),\min(f(v,j)+(i\neq j)) \}$$

$r=\max\{\min(g(u,i))\}$，时间复杂度$O(n)$。

反思：在分析问题的时候，我们通过发掘性质让我们的 dp 有的放矢。从简单问题入手，一步步发掘真相，类似于侦探的过程，这种是常见的思维技巧。

CF1517F Reunion

直接统计十分困难，考虑转化问题，不难发现可以把问题转化为统计半径$\ge r$ 的园的个数。但是如果你对这个进行计数 DP 的话你会发现这个极其容易算重，因为这个是存在问题。

我们考虑存在问题能不能转化为限制问题，这是计数问题中一个常用的思维技巧。不难转化为对于所有黑点周围$\le r$ 点的并集不是所有点，这个问题是一个染色问题，我们可以进行 dp。考虑状态中记录黑点往上覆盖的最远距离，或者是子树内最深的还没有被覆盖的点。这两个信息只有一个有效，因为如果子树内有没有被覆盖的点，设点$x$ 能覆盖这个点，那么点$x$ 的覆盖范围一定是子树内黑点往上覆盖范围的超集。

考虑设$f(u,i)$ 表示子树$u$ 内，$i\ge 0$ 则表明子树内黑点网上覆盖的最远距离是$i$，$i<0$ 则表示子树内最深没被覆盖点的深度为$i+1$，转移要分讨四种情况，时间复杂度$O(n^3)$。

反思：计数问题中所有限制问题优于存在限制问题。预计那这种会算重的存在性问题想一想能不能转化为限制性问题。

CF1368H1

一个显然的想法是建出来网络流的图，即$S$ 连蓝色接口，红色接口连$T$，矩形内的所有点也建出来，向四周连容量为$1$ 的无向边，然后对原图跑最大流就是答案。

显然会炸掉，考虑不能跑最大流，那怎么办，利用最大流最小割定理，我们可以把原命题转化为求最小割，转化一下就是把矩阵的所有点染蓝或者染红（代表最后和起点还是和终点联通），求所有染色方案下的最小端点异色边数。

考虑 DP，发现直接 DP 没太大啥用。考虑发掘性质，我们发现如果考虑整张图都是红色的情况下，那么割就是蓝色点数，现在问欧体转化为我们要把矩形中一些点改成蓝色使得割最小。那么有一个想法就是改点一定要挨着边界，让后要改要么改一整行要么改一整列。

那么有结论：最优染色方案一定是一整行或一整列颜色相同。对行 DP，翻转矩阵后对列再 DP 就可以了，时间复杂度$O(n)$。

反思：从高复杂度算法开始，一步一步进行优化，这个和从简单问题推广到更难的问题一样。

最大流问题如果无法优化可以转化为最小割问题。手算最小割属于是一个常见套路。

acg009c

区间 DP，设$f(i,0/1)$ 表示考虑到$i$ 个，第$i$ 划分到 A 或 B 的方案数。转移的话考虑$0\to 1,1 \to 0$ 即可，但是要满足两个性质：

• 区间内部满足条件。
• 区间两端满足条件。

让后发现第一个的决策集合是一个$[1,i]$ 的一个后缀，第 2 个是一个前缀。用前缀和维护，第一个用分段 for 处理，第二个双指针。

CF573D

好题，但是田忌赛马。

有一个显然的想法就就是二分图带权最大匹配(或网络流），但是时间复杂度是$O(n^3)$ 及其难受，考虑 DP 但直接 DP 十分困难，考虑发掘一些性质。

利用贪心思想，先对$w$ 和$h$ 进行从小到大的排序，一个基本思想就是对应位置的相乘，用调整法不难证明这是最优决策，但是本题目中存在第$i$ 个人不能骑自己的马，所以最优解可能不会取到。

考虑到这个限制只是限制自己不能骑自己的马，合理猜测$i$ 位置匹配马的决策是一个范围，有结论：匹配范围为$[i-2,i+2]$。证明考虑反证法，设$i$ 的禁止匹配位置为$ban_{i}$。那么反证法，假设如果在这个以外的范围选，那么最多向前会造成两次$(i,i-1)$ 无法匹配，自行画图发现这种情况最劣情况下也只会在$i-2$ 的情况形成匹配。

借用 _sys 的图：

完美匹配至少有三个红线和黑线相交整法不难证明如果两条线相交那么交换这两个匹配会得到更优的解。

让后考虑交换的过程，我们如果前$i$ 个人和前$i$ 匹马匹配完全，那么存在$k<3$，使得$[i,i+k]$ 这区间内的人和马匹配，可以用反证法证明。

故，设$f_{i}$ 表示前$i$ 个人和前$i$ 匹马完成匹配的最大全职，所以从$f_{i-3},f_{i-2},f_{i-1}$ 转移过来即可，同时改成矩阵方式维护 DP 做动态 DP 即可，时间复杂度$O(27n \log n)$，其中$27$ 是矩阵带来的常数。

提交记录

反思：限制过松的题目，我们可以通过强化限制使得题目范围的解缩小，让题目简化。

AGC009E

我太拉了，还是看 大佬 的题解吧。

反思：在具有强烈过程性的题目可以往结果的方向猜性质，观察性质的时候可以观察操作是否具有什么特殊性质，例如本题的$k$ 叉树。

CF1481E 还有 abc201F

不难发现每本书最多移动一次，移动多次一定是不优的。

把每本书的状态定义为 0/1 表示移动或不移动，枚举这本书的状态，如果以最后一本不动书为界限，那么前面的书那么前面的书如果属于同一种类，那么一定同时移动或者同时不移动，否则这本不动书就会使他们不能相聚。

所以我们枚举最后一本不动书，它后面的数一定要动，现在要决策它前面的书，其实就是选出来书种类的区间不能相交，那设$f(i)$ 表示前$i$ 本书中最大的不动书个数，预处理每本书左端点$l_i$ 和右端点$r_i$ 以及出现次数$cnt_i$ 就简单了。

反思：状态设计如果没有思路，可以尝试使用枚举法来设计状态，有助于思考。

同类型的题：abc201f

CF1474F

头脑风暴！

注意到$x$ 对答案一点用都没有，因为我们求的是长度，光一个$d$ 就能够确定答案了。

发现最长严格上升子序列的性质不太好刻画，我们考虑这个添加数的操作过程能不能以一种形式来表现出来。注意到每一个数具体取值只和最后一个数的变化有关，而且变化是连续的，考虑给它拍到二维平面上，横轴按照每一次添加一个数划分时间，纵轴为最后一个值的具体取值，原操作在二维平面上表现的是斜率为 1 或 -1 的一堆直线，如下图，红点表示一次插入操作的：

最长严格上升子序列的性质就很好刻画了，因为根据图来看其实就是最低点和最高点的极差就是我们的长度（因为斜率为$\pm 1$）。让后我们考虑这个子序列个数怎么解决。发现直接 DP 求解答案十分困难，考虑发掘性质，首先不难发现一个性质：一个段不可能贡献超过一种答案，即一个点不可能成为最低点或最高点。

这个性质有什么用呢，也就是说，我们可以统计对段的答案进行贡献统计。然而注意到段数极小（数据范围$n$），值域极大，有一个强烈的矩阵味道，但是我到现在连状态都没设计耶？

最长严格上升子序列可能从任意值拼过来，考虑在状态中加上这一个，设$f(i,j)$ 表示目前计算到第$i$ 段，末尾值为$j$ 的方案数，哎这矩阵味道对了，转移：

$$f(i,j)=\sum\limits_{k=0}^i f(k,j-1)$$

矩阵快速幂优化，时间复杂度$O(n^4 \log |V|)$。

Submission #333002703

反思：状态设计中需要是可考虑当前状态能否刻画子问题，不要受限于定居思维。

CF1463F

容易发现以最优解应是以某一循环节重复多次的形式。

考虑对循环节求解，发现数$i$ 的躯体取值仅和前$\max(x,y)$ 个数的选取情况有关，注意到$\max(x,y)\le 22$，考虑状压。因为循环节选取情况一样，所以我们只用遍历第一个循环节的数进行状压。

令$g=\max(x,y)$，全集为$U$。设$f(i,S)$ 表示在第$i$ 个点，前$g$ 个数选取状态为$S$ 的最优解。

记$t$ 表示$i$ 不选的选取状态，那么有转移$f(i,t)=\max\{ f(i,t),f(i-1,s) \}$。

若选，则要满足$i-x,i-y$ 没有被选，那么有$f(i,t+1)=\max\{ f(i,t+1),f(i-1,s)+val(i)\}$。

其中$val(i)$ 表示$i$ 能产生的贡献，具体的：若$L=x+y$，那么原串可以被分为多个长度为$L$ 的循环节，个数不妨设为$num$ 个，和最后的$n \bmod L$ 的遗留串，不妨设长度为$L'$。

若$i\le L'$，那么$val(i)=num+1$，反之则为$num$，故可以直接做。

MLE 了记得滚动数组。

反思：若状态转移过大的时候，考虑找规律，矩阵快速幂，或者找循环节。

Cf1188D

题目要求的就是求：

$$\min_{x\ge 0} \sum cnt1(x+\max a-a_i)$$

其中$cnt1$ 表示二进制位中 1 的个数，为了方便不妨令$a_i \leftarrow \max a-a_i$。

考虑如何求解这个式子，我们考虑按位规划，我们考虑以下信息：

• $x$ 在这一位规划的代价。
• 所有$a_i$ 在这一位的出现情况。
• $a_i$ 是否在之前的规划中出现过进位。

如果我们直接暴力状压进位的话，时间复杂度是$O(n2^n)$，及其难受，但是，我们考虑到如果只保留前$i-1$ 位，越大的$a_i$ 约有可能进位，如果我们把所有$a_i$ 排序后，那么发现进位的一定是$a$ 的一个前缀。故设$f(i,j)$ 表示考虑到第$i$ 位，有$j$ 个数发生仅为的最小代价，时间房租啊都$O(n\log n \log |a|)$。

反思：我们在 dp 优化过程中可以考虑只保留我们需要计算代价相关的状态，这是一个常见的 dp 优化方式。

CF1539E

首先答案可以抽象为 0/1 相间的串，进一步，可以把答案看作 0 一段，1 一段的串。

如果说，我们答案串里面有一串 0，区间在$[l,r]$，那么这一段给出的每一个数一定满足：

• $a_{l,i}\le k_i \le b_{l,i}$
• $a_{r,i}\le k_{l-1} \le b_{r,i}$

考虑到操作对后续有影响，而对前面没有影响，考虑倒着确定每一个数，倒着扫。维护 0 一段 1 一段的合法区间，每扫一个位置看看上面第二个条件是否满足，如果可以就转移。对于转移是否合法可以用布尔加与运算维护。时间复杂度$O(n)$。

反思：对于答案是 01 交错的题目，要有把答案切成许多全 1 或全 0 串的思路。对于值要满足后面会出现的限制条件，可以考虑倒着扫。

CF375E

注意到红色位置没有一丁点用，而且交换操作是很难记录的。注意到黑点总数是固定的，而且交换时任意位置进行交换，不妨考虑让子树内钦定放了几个黑点。

但是这个转化还没有解决$\le x$ 的问题，可以满足子树内（不包括$u$）的点满足条件，这么设计状态是可以的，但是如果包括$u$ 了就得直到谁给$u$ 产生贡献。如果第三维度加上距离$x$ 不好确定，因为贡献不唯一，但是如果我们钦定谁能解决$u$ 的问题的话那么问题就很好做了。

即，设$f(i,j,k)$ 表示$i$ 子树内放$j$ 个黑点，用$k$ 点解决$i$ 点距离的问题。满足的最小代价。

转移考虑枚举第三维这个点具体是什么，从儿子合并上来，有分类讨论：

• 若儿子$v$ 第三维$k'=k$：那么有$f(i,j+j',k)\leftarrow f(i,j,k)+f(v,j',k)$
• 若儿子$v$ 第三维$k' \neq k$：考虑到父亲肯定不会选儿子$v$ 子树内的点，孩子也不会选子树外的，证明可以考虑调整法。 那么我们合并完$f(i,j+j'.k)$ 之后直接找到对于每个$v$ 子树内$k'$ 对应最小的$f(v,j',k')$ 转移即可，时间复杂度$O(n^3)$。

反思：问题前后相互影响的时候，或者操作是全局的，可以尝试把操作部分定义到局部变量里面跟翻遍我们去处理。

卡空间，用 short 即可：

提交记录

P5289 皮配

题面过于复杂，有一个显然的想法就是让导师们去找学生，设$f(i,j,k,p)$ 表示四个导师选的人数状态下的方案数，转移判断满不满足题目中所给的派系和阵营限制即可，时间复杂度$O(nm^4)$，不难发现只需要确定三个即可，时间复杂度$O(nm^3)$。然后就不会了。

观察这个 DP 及其难以优化，因为如果我们缺任何一个信息都无法描述完整的子问题，而且复杂度要求的可是$O(nm)$，你只知道一个信息那么肯定啥也导出不了啊。我们考虑发掘几个性质：

• 确定一个派系和一个阵营可以唯一确定一位导师。
• 题目中 ban 导师的相当于不选钦定的派系和阵营。

上述性质启示我们让每一个学生去确定它们的派系和阵营，而不是导师去确定学生。但是还有我们的 “坏” 学生，不喜欢选的。我们先丢掉它们，先考虑$k=0$ 的部分分。

有一个显然的 DP 就是$f(i,j)$ 表示$i$ 个蓝阵营的人，$j$ 个鸭阵营的人的方案数，剩余两个可以由这两个状态唯一表示出来，时间复杂度$O(nm^2)$，仍无法通过。正解启示$O(nm)$，考虑进一步发掘性质：

• 题目中学生来自的城市限制，和学校限制是互相独立互不冲突的。

这个性质启发我们分离上面状态设计中的$i,j$。那么不妨设$f(i)$ 表示蓝阵营有$i$ 个人的方案数，$g(i)$ 表示鸭阵营有$i$ 个人的方案数，两个答案可以通过乘法原理分别算出来之后乘起来即可，时间复杂度$O(nm)$。

现在考虑$k>0$，一个重要的观察是$k\le 30$。状压、枚举？都不对。我们上面的计算答案过程中体现了乘法原理的思想，也就是说我们也可以分离 “坏学生” 和 “好学生”，好学生单独做，坏学生单独做，最后乘起来即可。

坏学生的限制怎么处理，我们肯定不能用$O(nm)$ 的算法了，这个算法肯定是无法处理我们的限制的。回看我们之前$O(nm^2)$ 的解法，这个就能够很好的处理性质，因为状态能够表示所有派系阵营选择人数，我们可以用这个算法处理坏学生就可以啦。时间复杂度做的话是$O(k^2sm)$ 的。

那么时间复杂度就是$O(nm+k^2 sm)$。

总结：

• 我们在设计状态的时候，应当尽量个限制紧密贴合。在优化 DP 的时候我们要考虑我们计算贡献具体需要什么信息，我们需要什么信息就足够了，去掉冗余的无用信息。
• 题目可能会故意引导你走向死路，如果一个方向想不通，不妨正难则反或换一种方法想，这里体现的是正难则反的思路。

P7214 治疗计划

把未感染和感染抽象为 0/1，那么原问题可以转化为初始有一个全为$1$ 的序列，可以在特定时间进行一次区间覆盖操作（有代价），$1$ 会向左右扩散，问能不能将整个序列全部覆盖为 0 且使得操作代价最小。

对于选择区间进行覆盖的问题，这一类经典问题有一种状态设计就是设$f(i)$ 表示将$[1,i]$ 这个前缀进行覆盖的最小代价。但是问题在于这样转移是$O(nm)$ 的不太好搞，考虑这个$m$ 的瓶颈就是在于我们需要知道每一个覆盖区间右端点在哪里。考虑切换一下 dp 状态，设$f(i)$ 表示将$[1,r_i]$ 覆盖的最小代价，转移通过$t$ 的偏序关系进行转移：

$$\begin{aligned}f(i) & \leftarrow f(j)+c_i & r_j -l_i+1 \ge |t_i -t_j| \end{aligned}$$

时间复杂度还是$O(nm)$，无敌了。而且还自带两个偏序关系更是逆天。但是观察这个 DP 是一个类似于最短路形式的转移（说人话就是转移代价只和目标的代价有关），考虑用 Dijkstra 优化这个 DP。让后绝对值可以通过对$t$ 排序去掉，对于转移可以用线段树优化这个最小值转移，势能分析有时间复杂度$O(n \log n)$。

总结：

这个题目有一个巨大的卡阻就是在于 DP 容易选择会以时间作为主体，这样的话你无论怎么都无法优化掉时间这一维。一开始想的就是$f(i,j)$ 添加了时间$j$ 这一个维度，但是发现这个枚举时间反而成为了瓶颈。这个时候，我们需要分析，我们知道什么就够了。分析下来$j$ 反而可以从转移中天然的去掉，这样我们就做到了优化 DP 的过程。

CF553E

考虑倒着 DP，设$f(i,j)$ 表示第$i$ 个点走到$n$，当前时间为$j$ 的期望。有转移：

$$f(u,j)=\min_{v\in son(i)} \{ \sum_{k} f(v,j+k)\cdot p_{u,k} \}+w_i$$

末状态$f(u,i)=dis(u,n)+x,i>t$，$f(n,i)=0,i\le t$

时间复杂度$O(nt^2)$，无法通过，考虑优化，发现一堆优化板子都套不上去，但是发现 FFT 可以套上去。考虑 FFT 优化，但是注意到这个玩意差卷积不能卷因为这玩意是半在线的。考虑分治 FFT，但是对什么进行分治呢？考虑分析转移方程，注意到方程中时间的转移时具有顺序的，可以进行 CDQ。不妨对时间一维分治。

具体的，记$g_{(u,v),j}$ 来表示$\sum_{k=1}^t p_{(u,v),k} \times f(v,j+k)$，用$f \to g$，在分治底层计算出$f(u,j)=\min_{v\in son(i)} \{ \sum_{k} f(v,j+k)\cdot p_{u,k} \}+w_i$，时间复杂度$O(mt\log^2 t)$。

好消息是又学会了一个科技。

反思：DP 优化不仅仅可以从状态优化和一类特殊的转移优化，也可以通过转移的顺序进行优化。

P3226 集合选数

纯纯构造题，首先$1\le n \le 20$ 可以通过状压枚举子集做到$O(3^n)$，通过高位前缀和有$O(n2^n)$。当然这都不是重点，问题是$n\le 10^5$。

考虑分析性质，先简化问题，从只有$2x$ 的性质。考虑转化模型，让$x\to 2x$ 连边。那么分析图性质不难发现图形成了一条一条的链，那么原命题相当于在上面求解独立集。

接着考虑$3x$ 的性质，让$x\to 3x$，发现图转化为了如下的形态：

那么不难发现图形成了网格图的结构，但原命题相当于还是在上面求解独立集问题。分析这个网格图，发现行数大约为$\log_{2} n$，列数大约为$\log_{3} n$，数量极小。考虑状压求解独立集即可。设$f(i,S)$ 表示考虑到第$i$ 行，一行选取数状态为$S$。预处理合法状态转移即可。

总结：

我们可以通过图论等模型来对题目性质进行进一步转化，同时从简单问题出发，一步一步添加限制也是一个思维角度，在添加限制的过程中会发现一些奇妙的性质。

CF830D

这玩意好像直接 DP 求发现我们无法确定这个转移顺序和 DP 主体，有可能是路径长度或者树本身。考虑从这个图发掘一些性质，手摸几个小深度的不难发现一些小性质（仅对正解有启示作用）：

• 一定存在经过所有点的路径（即哈密顿路径），且路径起点终点一定是叶子，这个路径一定算入答案中。
• $k$ 树的两个孩子由$k-1$ 树构成，同理$k-1$ 两个孩子由$k-2$ 树构成 ，以此类推。
• 路径可以看作一条有向链。

由于仅对正解起启示作用，故不给详细证明。性质 1 的证明可以归纳法证明，由叶子到叶子的哈密顿路径可在每个父节点处用左右子树的哈密顿路径路递归拼接得到，因此总能存在经过所有顶点的简单路径。

同时结合性质 2，任一节点的子树在哈密顿路径中必须整体连续出现，且路径端点必是叶子，因此全局路径只能自底向上由叶子路径块依次合并成更大的块，否则无法覆盖所有组合且会漏算。启示我们 DP 的主体以树为主体而非路径长度，顺序为自底向上合并。

让后设$f(i)$ 表示$i$ 树的贡献，但是发现合并贡献的时候不知道信息，考虑添加一维$j$ 表示有$j$ 条路径链的方案数。转移如下：

$$f(i,j) \leftarrow \begin{cases} f(i-1,k)\cdot f(i-1,j-k) & \text{不算根} \\ f(i-1,k)\cdot f(i-1,j-k-1) & \text{算根} \\ f(i-1,k)\cdot f(i-1,j-k) \cdot 2k & \text{根合并一条} \\ f(i-1,k)\cdot f(i-1,j-k+1) \cdot k(k+1) & \text{根合并两条} \\ \end{cases}$$

时间复杂度$O(n^3)$。

提交记录

总结：

DP 顺序和方案顺序是不一样的，这道题通过类似于自底向上的合并顺序将若干条（有向）路径合并到一起。

有的时候不好确定 DP 主体和顺序的时候，可以考虑发掘一些小性质，通过小性质将不合法的转移顺序排除。

路径问题可以看作几个有向链的合并过程。

gym102538H

这道题和上面一样，也是路径计数问题并且考虑的是有向链的合并过程。

首先考虑转移顺序，分析性质发现：

• 成环的部分一定是$1[a_i]$ 所覆盖的。
• 环可以拆成两个有向链。

考虑 DP，首先对$a_i$ 排序从小到大覆盖区间，简化问题。每次增量一个左部的点，然后考虑它连出去的两条边，达到的效果就是合并两条路径。

设$f(i,j)$ 表示当前考虑前$i$ 个点，形成了$j$ 条路径，转移有两个：

• 添加$a_i -a_{i-1}$ 个右部单点：$f(i,j)=\sum_{k=0}^{a_i-a_{i-1}} f(i-1,j-k) \cdot \binom{a_i-a_{i-1}}{k}$。
• 取两条路径合并：$f(i,j)=f(i,j+1)\times j(j+1)$。

时间复杂度$O(n^2)$。

总结：上面两道题给我们了对路径计数问题的一种新看法：有向链的分散与合并。DP 的顺序和方案顺序可能并不一致。

CF235D

首先很难发现这玩意就是让你求概率而并非期望，因为递归次数可以分配到每个点上，权值为 1，所以答案就是概率求和。

让后考虑概率怎么求，先定义概率是什么，我们发现如果一个点$u$ 要想给另一个点$v$ 组合，即选取点$u$ 为点分治中心，中心与$v$ 联通的概率。贡献的话，那么必须要保证$u \to v$ 的路径上必须没有点被删，即$u$ 是第一个被删的。大胆猜想概率就是$\dfrac{1}{dis(u,v)}$，考虑证明用归纳法证明：

• 若直接删除$u$，概率就是$\dfrac{1}{n}$。
• 若没有删除，那么贡献必须保证删除点之后$u,v$ 联通。删除一个点的概率为$\dfrac{n-dis(u,v)}{n}$，子图内概率为$\dfrac{1}{dis(u,v)}$，故这种情况概率是$\dfrac{n-dis(u,v)}{n \cdot dis(u,v)}$

不难发现加起来就是$\dfrac{1}{dis(u,v)}$，暴力枚举点对时间复杂度$O(n^2 \log n)$。

考虑放到基环树上怎么做，发现这个$dis$ 会出现环上两个路径的问题，概率上这两个路径的权重是等价的。考虑如何同时统计两个环上路径的概率，发现很难统计会算重。正难则反，考虑不遍历环，我们直接容斥，设两个路径长度分别为$x,y$，令$u,v$ 到自己树根的距离为$dis(u),dis(v)$，那么容斥就是$\dfrac{1}{dis(u)+dis(v)+x}+\dfrac{1}{dis(u)+dis(v)+y}-\dfrac{1}{dis(u)+dis(v)+x+y}$，即多算了两个路径都联通的贡献，时间复杂度$O(n^2 \log n)$。

总结：

合理利用期望的线性性，要分清是求期望还是概率，别一上去发现求的是概率就搞笑了。

从简单往难推是一个合理的思考思路。

CF1608F

有一个显然的想法就是状压所有我们选过的数，发现时间复杂度是$O(n2^n \log |V|)$，及其难泵，考虑分析 mex 运算的性质。

• 当前$a_i$ 选的数比 mex 大，mex 取值不变，同理选的小，不过我们不考虑小的情况从小到大选。
• 每个位置 mex 的取值是具有限制的。是一个值域范围。

我们考虑我们的状态设计，我么需要在规划完前缀$i$ 的时候得到它的 mex，也就是我们的状态必须有这两个维度。除此之外我们还需要所有大于 mex 的值才能让我们转移 mex，但是这不又回到了状压了吗？

我们考虑寻找大于 mex 的等价性，如果我们在一个数对 mex 产生贡献的时候再去计算的话就可以啦。设$f(i,j,k)$，表示目前到第$i$ 个，大于 mex 的数为$j$ 个，但是我们未确定这些数，mex 为$k$ 的方案数。

• $a_i < k$，对$mex$ 不会造成影响：$f(i+1,j,k) \leftarrow f(i,j,k) \cdot k$
• $a_i > k$，对$mex$ 不会造成影响，但是要考虑它是归入已有的未确定的值中：
  $f(i+1,j,k) \leftarrow f(i,j,k) \cdot j$；
  还是新增一种未确定的值：
  $f(i+1,j+1,k) \leftarrow f(i,j,k)$
• $a_i = k$，我们改变$mex$ 变成$t$（$t > k$），那么需要用卡未确定的值来填补$(k,t)$ 的这一段，
  方案数就是排列数$A^{k-t-1}_j: f(i+1,j-(t-k-1),t) \leftarrow f(i,j,k) \cdot \frac{j!}{(j-(k-t-1))!}$

时间复杂度$O(n^2 k^2)$，考虑优化，我们把最后一种转移优化一下，把状态偏移：$f'(i,j+k,k)=f(i,j,k)$，最后一种转移可以对第三维做前缀和，其他转移同下：

$$f'(i+1,j,k) \leftarrow j\cdot f'(i,j,k) \\ f'(i+1,j+1,k) \leftarrow f'(i,j,k) \\ f'(i+1,j+1,t) \leftarrow f'(i,j,k)\cdot\frac{(j-k)!}{(j-t)!}$$

时间复杂度$O(n^2 k)$。

总结：

• 能需要根据限制的特性，提前或延迟确定一些元素的过程。

HDU 6566

有一个$f(i,j,0/1)$ 表示$i$ 子树内权重和为$j$，当前点选不选的最大权值。时间复杂度$O(Tnm^2)$ 无法通过。考虑优化，我们用 dfs 序转移来进行优化，但是发现 dfs 序从$i\to i+1$ 的时候进行转移，若 $i+1$ 对应的节点在 $i$ 对应的节点的上方时，就可能不知道$i+1$ 选取的情况，而且暴力状压是不行的。

发掘性质，dfn 相邻的点的移动轨迹一定是往上跳若干步然后往下走一步（这个性质很有用），官方题解告诉我们先进行轻重链剖分 然后划定 dfs 序的时候最后遍历重儿子 这样你在 $i\to i+1$ 的时候会直接跳过上面的一段重链，我们发现对于每个点只需要记录每个重链的链底就好了，由轻重子树剖分性质不难有状压状态数为$O(2^{\log n})=O(n)$。

设$f(i,S,j)$ 表示考虑到 dfn 为$i$ 的点，当前根的链底的点状态为$S$，已经用了容量为$j$，转移可以写成$O(1)$，时间复杂度$O(n^2m)$。

反思：头一次见树形 DP 还可以转到 DFS 序上进行操作，属于是切换了转移顺序。发现就是如果你切换转移顺序可以利用切换至后带来的特殊性质，使得状态是可以减小。

P7213

这题真是无敌了，想 30 分钟结果连状态都没设出来。

直接 DP 发现没有什么好玩意，考虑发掘一些性质，发现性质是真 dmt 的难找：

• 序列 A 所代表的末状态$h$ 所构成的集合其取值一定是一个$[1,n]$ 的排列。
• 震柱子从 2 到 1 一定是值域从大到小震。
• 操作造成贡献是对值域上位置最靠后的值操作。

由上面三个操作可以一个操作的导出：从值域上从大到小，我们将两个位置位置靠前的减。发现这个没有什么前途因为我试了 www。

考虑性质都是从位置靠后的值操作，有一个操作直接导出就是位置从后往前扫，维护当前值最后一个出现的位置，如果没有出现过，就维护不变，否则减 1。

让后发现每一次都要执行这个操作，如何做到$O(n)$ 而不是$O(n^2)$ 操作，发现如果当前柱子之后有高度为 $1\sim h$ 的柱子各一根，那么当前柱子及之前的柱子，如果高度 $\le h$，都会被直接震没。

发现这个玩意及其有用，我们考虑在这个上面 DP，借鉴 CF1608F 的思路，设$f(i,j)$ 表示进行到第$i$ 个，取出集合最大值为$j$ 的方案数。

方便转移，我们需要设定几个参数：

• $cnt0$：表示后$i-1$ 钦定消失的数量。
• $cnt1$：表示后$i-1$ 钦定存在的数量。

此外需要区分一下同样高度的两个柱子（比如染色）以便转移，最终答案就需要除掉 $2^n$。

分类讨论：

• 如果$i$ 钦定消失，那么$j$ 不变，从$f(i-1,j)$ 转移，此时有$2j$ 个可用高度，而$j$ 个给了取出集合，还有$cnt0$ 个已经钦定，那么系数就是$j-cnt0$。
• 如果$i$ 钦定保留，我们同样考虑它的$h$ 取值：
  • 如果$h_{i}>j+1$，我们只能稍后进行确定，从$f(i-1,j)$ 转移系数为 1。
  • 若$h_{i}=j+1$，有些标准柱的高度还未确定，所以我们需要考虑接起来之后的高度阈值。我们枚举一个最大值$k$，此时从$f(i,k)\to f(i-1,j)$，计算系数有：
    • 选定位置$\dbinom{cnt1-j}{k-j-1}$。
    • 确定当前长度$(k-j+1)$。
    • 考虑$k-j+1$ 的形成方案数，令其为$g$。
      乘起来即可。

现在考虑$g$ 的转移，我们枚举最后产生的高度$j$，那么有：

• $h\le j-1$ 和$h> j+1$，显然不会互相产生影响。这部分的系数为$g_{j-1}\times g_{i-j}$。
• $h\le j-1$ 和$h\ge j+1$，排列总方案数$\dbinom{i-1}{j-1}$。
• 考虑$j$ 的方案数，共$2(i-j+1)$ 个高度可以选择，但是$i-j$ 已经被选了，所以还剩下$(i-j+2)$ 种方案。
  转移乘起来即可，时间复杂度$O(n^3)$。

总结：

这个题实在是太复杂了，即运用到 CF1608F 的延后确定值的思想，又有许多的特殊性质，这个题提取出的精华就是这种延后确定值和钦定值的思想。

P2048 [NOI2010] 超级钢琴

不难发现答案要求的就是前$k$ 大。

先考虑$k=1$ 如何做，有一种做法先前缀和，让后固定左端点$l$，那么其对应的右端点区间就是$[l+L,l+R]$，用 ST 表查这个区间对应的最大值前缀和就可以取到多大就可以了。对每一个$l$ 做一遍时间复杂度是$O(n\log n+n)$，瓶颈在 ST 表预处理。

接着考虑$k>1$ 如何做，考虑求前$k$ 大的一个经典技巧：用堆维护状态，但要保证堆内情况能做到不重不漏遍历所有情况。

发现每一个左端点对应唯一一个大根堆（以前缀和权值）笛卡尔树，我们可以考虑类似于遍历笛卡尔树的过程进行操作。具体的，先遍历所有$l$，都做一遍$k=1$ 的操作，让后设定状态$(l,L,R,val,pos)$ 表示左端点在$l$，管辖区间为$[l+L,l+R]$，当前状态点最大权值为$val$，决策取在$pos$ 这个右端点。把所有左端点的答案丢进以$val$ 决策的大根堆，让后取出堆顶，记录答案，让后类似笛卡尔树一样，把这个以$pos$ 劈开成$[L,pos-1],[pos+1,R]$，重新求$val$ 加入堆里面，重复做$k$ 次即可。

大部分题解的做法可以归类到笛卡尔树的结构，但是我在课上说这个大概是一车人没听懂。

总结：前$k$ 大/小 的权值可以通过用堆来维护状态，但是我们在用堆来进行维护的时候要做到不重不漏的遍历所有情况，状态的设计是一个重要思路。

CF1060F Shrinking Tree

这题状态涉及真有点巧妙和困难吧？

直接飞上去树形 DP，发现坠机了。考虑发掘一些性质能够，首先规划一个复杂度目标是$O(n^4)$。

• 根不固定，答案一定和子树大小有关。
• $u\to v$ 进行边缩点操作，不妨最后得到的点为$u$，那么$v$ 的儿子会全部接到$u$，产生新的限制。
• 操作是全局的，如果我们无法确定子问题操作顺序的话我们无法确定合理的 DP 顺序。

先确定 DP 主体，我们要对断边的顺序进行概率 DP，将这些概率求和之后除掉$(n-1)!$ 就可以啦。

让后解决性质带来的问题，对于第一个性质（问题）的解决，我们可以考虑通过枚举法枚举树根给他固定下来，让后钦定这个点是我们最后缩点剩下的点，让后在进行 DP。

发现第二个性质和第三个性质是绑定在一起的，因为如果我们不知道操作顺序的话我们也无法知道缩点之后产生了多少新的限制。先考虑第二个性质，断边之后会带来新的限制，我们可以规划到$v$ 的子问题，就是单独考虑$v$ 的时候这些边不能让$v$ 被消掉。

而对于第三个性质，有一个 Trick：全局操作可以将操作设进局部状态内。具体的，这里的新限制一定是在删除$(u,v)$ 这条边之后产生的，我们状态中需要记录操作的时刻。设$f(i,j)$ 表示$i$ 子树内，删除顺序中后$j$ 条边不让$i$ 点被消掉的概率。同时记$g$ 表示只考虑子树$v$ 和边$(u,v)$ 的概率。

转移考虑枚举$(u,v)$ 断开的时间$j'$：

• 若$j'\le j$：那么我们必须要乘上$\dfrac{1}{2}$ 的概率，后面的$j-1$ 条边需要改接到$u$ 上。转移就是$g_{j}\leftarrow \dfrac{1}{2}\cdot f(v,j'-1)$。
• 若$j>j‘$，那么$(u,v)$ 和我们没关系，这条边会提前断开，但是仍然需要考虑那些改接到$u$ 上的边，所以$g_{j}\leftarrow f(v,j)$。

求出辅助$g$ 之后我们可以背包得到新的$f_{u}$。因为我们还需要规划断边的顺序，而子树间的断边是互不影响的，所以可以直接用组合数计算方案数，保证考虑到的边和没考虑到的边之间的顺序即可：

$$f'_{u,i+j}\leftarrow f_{u,i}\cdot g_j\cdot{i+j\choose i}\cdot{siz_u-i-1+siz_v-j\choose siz_v-j}$$

答案就是$\dfrac{f(i,n-1)}{(n-1)!}$，时间复杂度$O(n^4)\to O(n^3)$，优化是前缀和优化。

总结：

全局操作可以通过转化例如本题的记录时间转化到局部状态内部。

对于变量我们可以通过枚举法帮助我们进行决策，同时寻找状态之间的不动点。

寻找子问题最重要的是找状态之间的相似性，所谓相似性的含义就是信息记录在子问题中的一部分的占比，本题目中我们通过构造不动色这一相似性来让我们的子问题可以刻画。

WC2022杂题选讲 stars

为什么我搜不到题啊？

一颗星星可以抽象成$k$ 维空间中的一个整点。称若干星星构成的集合$S$ 是奇妙的，当且仅当在$k$ 维空间中的整点$P$，$P$ 与$S$ 中的每颗星星至少有一维坐标相同。
有一个长度为$n$ 的星星序列$A$，请你求出所有奇妙子区间的个数之和。
$1 \le n \le 10^5, 1 \le k \le 5$

触发敏感词 “存在”，联想到 CF1517F 战败经历直接哈气转限制问题。首先$k$ 很小，可以暴力枚举法来确定我们坐标的相同的限制。

有了这个思路，我们来判断$S$ 中集合是否是奇妙的。我们首先把$S_{0}$ 拿出来，暴力枚举我们钦定的第一个相同的位置。让后接着往后遍历，遇到一个不符合相同的，就在暴力枚举一个，一直往后做直到方案可行即可。

发现上述的过程就是在枚举一个$p$ 的排列，按照这个排列钦定即可（也可以不用全部都用），让后我们要把他搬到计数上，首先发现排列数级别在$O(5!)$，数量 120 极小，可以直接加进 DP 状态内。

倒着扫更方便我们处理，设$f(i,S)$ 表示我们扫到第$i$ 个，钦定顺序为$S$ 的情况下，最远能拓展的距离。发现直接转移是十分困难的。

写出转移需要强大的观察能力，我们可以观察子问题之间的相似性来进行转移，我们考虑$f(i,S)$ 和$f(i+1,S')$，其中$S'$ 为去掉$S_{0}$ 的排列。只是对于$f(i+1,S')$ 第一个需要新增元素但是可以被$S_{0}$ 解决的位置是不需要新增的，我们可以让$S_{0}$ 去解决，所以我们把$S_{0}$ 插入到当前最后一个锦囊的下一个位置就得到了$i+1$ 的等效子问题，也就是对于以后的影响都等效地传递下去了。

时间复杂度$O(nk\cdot k!)$。

总结：

发现之前 DP 的做法顺序有一定的问题，我自己在做 DP 的问题在发掘完性质后就直接开始设置状态，我们在这些过程中融入了一个看似缺失的步骤：寻找子问题。

状态是对子问题的抽象描述，而子问题是状态所对应的具体计算问题。

为什么说是抽象地描述，前面我们所一直重复提及的 “最优最简状态” 的状态优化，就是在设出状态后要通过一系列的抽象化将状态变得简洁且更易计算。而我们状态的抽象化的前提是你的抽象化能够完整导出整个子问题才可以。

那么如何刻画子问题，需要把已经被当前处理的影响“消除”或封装好，让子问题状态只包含“未来的必需信息”，不受当前操作遗留的后效影响。我们将其简称为：“消除后效性”。

而寻找子问题最重要的是找状态之间的相似性。所谓相似性的含义就是信息记录在子问题中的一部分的占比，相似性越大你写转移就越容易，换句话说就是两个状态在未来计算中共享的“信息/行为”比例。

意义在于：高相似性可以让转移方程更统一、简洁，相似性越大你写转移就越容易，而低相似性转移方程复杂、需要处理很多特例。这也就是为什么转移方程有的时候及其难写，根本原因就是在于相似性程度低，状态太细，信息的共性没有利用，未来影响无法统一处理。

这需要强大的观察力和性质分析来分析这个相似性。

回到本题，为什么我们无法写出来转移方程，因为我们没有发现相似性。等效子问题就是一个关键相似性，等效子问题把复杂的状态差异“折叠”掉，只保留对未来影响的核心信息。

于是可以总结一个关键操作：当某个元素的决策影响很远，但 DP 每次只能一步更新时，通过找到一个当前问题的等效子问题，可以把这个远程影响一次性传递给下一步，实现高效转移。

求"满足某种条件的子串/子序列"的长度和、个数。
若无思路可以先考虑如何判断合法，再试图通过 DP 求得答案。

收获的地方就是在于遇到转移方程难写的时候，我究竟应该干什么了。还有等效子问题的优化方法。

CF1439D INOI Final Contests

我们是对$a,b$ 进行计数，发现没有空位的情况下是十分好做的，思路就是把人分配到空位置里。但是有空位的情况下就不太好做了，但是借鉴之前的思路，将位置分配给人。

设$f(i,j)$ 表示考虑$i$ 个位置，$j$ 个人情况下的贡献，同时需要方案数方便进行转移，设为$g(i,j)$，定义同前。转移考虑分类讨论，有两种情况：$i>j$ 和$i=j$。即有空位和无空位：

• $i>j$：有一个想法就是我们可以通过空位划分子问题，考虑边缘的空位是限制最小的，枚举空位$k$，划分为$i-k-1$ 和$k$ 的子问题。有转移：

$$g(i,j)=g(i-1,j)+\sum\limits_{k>0} g(i-k-1,j-k)g(k,k)\cdot \binom{j}{k}$$

$$f(i,j)=f(i-1,j)+\sum\limits_{k>0} (g(i-k-1,j-k)\cdot f(k,k)+g(k,k)+f(i-k-1,j-k))\cdot \binom{j}{k}$$

• $i=j$：这个时候就不能套用上面的做法，但是我们枚举最后一个人的最终位置$j$，同时通过这个划分为两个子问题，令$sum(x)=\sum\limits_{i=1}^x i=\dfrac{x(x+1)}{2}$，有：

$$g(i,i)=(i+1)\sum\limits_{j=1}^i g(j-1,j-1)\cdot g(i-j,i-j) \cdot\binom{i-1}{j-1}$$

$$\begin{aligned}f(i,i)\leftarrow \sum\limits_{j=1}^i (sum(i-j)+sum(j))\cdot g(j-1,j-1)\cdot g(i-j,i-j) \cdot \binom{i-1}{j-1} \end{aligned}$$

$$\begin{aligned}f(i,i)\leftarrow (i+1) \sum\limits_{j=1}^i f(j-1,j-1)\cdot g(i-j,i-j)+f(i-j,i-j)\cdot g(j-1,j-1) \cdot \binom{i-1}{j-1} \end{aligned}$$

时间复杂度$O(n^3)$。

总结：

这道题就是枚举法划分子问题的巅峰神作之一，总和运用枚举法划分子问题。本题目就是通过限制设置分界线，将一个子问题划分为两个子问题，最后是转移的时候选限制最小的方式转移。突然发现枚举最大值 DP 这玩意和这个极其类似，通过枚举最大值划分子问题。

CF461E Appleman and a Game

神仙题，不是思路神仙，而是带来的收获很神仙。

先考虑我们直到$s$ 的情况下如何求最小，一个显然的想法就是建出 SAM，让后把$s$ 丢到$SAM$ 匹配，如果新加入字符使得当前状态不是子串，直接回到根节点，让后添加 1 的操作（SAM 能表示$t$ 的所有子串）。

让后我们对$s$ 计数，当然也可以这么做，设$f(i,j)$ 表示当前进行到第$i$ 个字符，SAM 自动机状态在$j$ 的最小方案数。转移枚举新插入的字符$c$，让后考虑状态$j$ 的变化。时间复杂度$O(n|t|)$ 直接爆炸，考虑优化。

发现及其难以优化，因为这玩意瓶颈就是在于枚举字符了，于是，我们使用刚刚学到的新技巧：“大步小步转移”

那么什么是大步小步转移呢？

• 小步：每次转移只做最细粒度的一步，比如一次只加一个字符、只处理一个元素、只走一步图边。小步适于考虑转移，但是可能会消耗更多时间
• 大步：一次转移跨过多步，把若干个“小步”打包成一个“段”直接跳过去。例如矩阵快速幂，倍增优化 DP。大步常常会很复杂，但是可能起到加速的效果。

我们尝试增大转移跨度，我们考虑操作次数为$k$ 的时候，能解决长度$x$ 以内的所有字符串，这个$x$ 最大时多少。

我们发现这个玩意毕竟和原命题不太类似，但是我们可以通过二分答案$k$，若$x<n$ 则$k$ 合法，最后的答案就是$k+1$。

虑这个新问题怎么设计状态，一次操作对应着一段字符串，要满足相邻两个字符串之间不能产生 $t$ 的子串，充要条件就是前面一个字符串在末尾添加上下一个字符串的第一个字符不能是 $t$ 的子串。

这说明我们只需要记录开头一段的第一个字符，设$f(i,c)$ 表示$i$ 次操作，开头段的第一个字符是$c$。能构造出来的字符串最短时$f(i,c)+1$，设$g(c,d)$ 表示字符$c$ 开头，末尾为$d$ 之后就不再是子串 的最短子串。那么转移拼一段上去：

$$f(i,c)=\min_{d}g(c,d)+f(i-1,d)$$

通过矩阵快速幂加倍增二分可以做到$O(|t|^2+\log n |t|)$。

总结：

移的大步小步。小步适于考虑转移，但是可能会消耗更多时间；大步常常会很复杂，但是可能起到加速的效果。我们经常先用小步确定规则，再用大步优化效率。在大步小步之间切换，才能写出合适的转移。

CF559E Gerald and Path

wc，这题 3 个解法简直就是层层递进，一步一步接近真相。

这题完全有必要我单独写一篇题解。

解法 1

我们发现这个线段既可以向左延申，也可以向右延申。但是有一个问题就是重复被覆盖的，我们不能把他计入贡献，例如下面三种情况：

• 两个线段$i,j$ 不交。
• 线段$i,j$ 只交一部分。
• $i$ 把$j$ 完全包含。

由于这道题覆盖多次只计入单次贡献，所以转移顺序不能混乱。

先把状态设出来，发现长度延申只和处于最右端的线段决策有关，故设$f(i,j,0/1)$ 表示前$i$ 个线段，右端点最靠右的线段是$j$，朝向为左或右，所得到的最大覆盖长度。

考虑转移，转移我们要从状态向后拓展，考虑下一个产生贡献的线段$k$，新增的贡献长度为$\min(len_{k},r_{k}-r_{j})$（它最多能延伸自己长度，但若它和前面线段有重叠，只能算到不重叠的部分）而中间线段$[i+1,k-1]$ 的处理，如果这些线段如果完全在$k$ 的范围内，我们钦定它们方向让它们被覆盖，相当于忽略它们的贡献。 ——这步是本题的关键：否则你会担心“是不是算少了”。但实际上算少不会影响正确性，因为最优解一定会被统计到；而乱算反而会导致重复覆盖。

转移时间复杂度$O(n^3)$。

总结：思考转移顺序是十分重要的，在覆盖 / DP 问题里，很多时候覆盖多次只算一次，或 顺序影响贡献。如果顺序乱了反而会把贡献重复统计，所以要设计合适的转移顺序。

忽略思想是转移顺序中的一个重要一环，同时也可以将一些不优解算入答案，只要不影响最终答案即可。

解法 2

大家还记得 Lantern 把，那么覆盖一段前缀的设计。

这里我们先把$a_{i}-b_{i},a_{i},a_{i}+b_{i}$ 这些位置都离散化，考虑最终点亮的情况一定是若干个不交的段。转移的关键就变成了判定段是否合法，用 Lantern 的方法求出$g(l,r)$ 表示用点$[l,r]$ 之间的线段是否能够覆盖$[l,r]$ 这些点，用$f_{i}$ 表示前$i$ 个点的答案，有转移：

$$f_{i}=\max(f_{j-1}+s_{i}-s_{j})$$

转移条件$g_{j,i}$ 为真，时间复杂度$O(n^2 \log n)$。

总结：思考最后答案的形式，可能会帮助你把最优化问题转化为判定问题。寻找子问题要考虑消除后面操作的影响。

解法 3

既然覆盖条件不好求，正难则反，直接计算不被覆盖的区间付出代价，现在目标变为用尽量少的“代价边”覆盖所有点。

设$f(i,j)$ 表示用前$i$ 个点的线段覆盖前缀长度$j$ 的最小代价。

如果线段向右覆盖：

$$f(i,r_{i})\leftarrow f(i-1,k),i\le k < r_{i}$$

如果线段向左覆盖，需要加一个$g(i,j)$ 表示第$i$ 条线段向左倒。通过前缀最小值优化转移。

另外还要加上使用“代价边”的情况：

$$f(i,i)\leftarrow f(i-1,i-1)+(p_{i}-p_{i-1})$$

时间复杂度$O(n^2)$。

【UER #6】逃跑

答案求的是$Dx$，可以写作$E(x^2) -E^2 (x)$，用线性性拆括号即可做到，这个$x$ 就是我们新经过的点数，而$x^2$ 表示两两配对。

考虑预处理$g(i,x,y)$ 表示过了$i$ 的时间走到$(x,y)$ 的期望，可以$O(n^3)$ 简单递推，这个玩意是基础我们先求才能地推出其他东西。同时令$pw_{i}=(w_{1}+w_{2}+w_{3}+w_{4})^i$。

考虑求解$E(x)$ 需要我们求单点对期望的贡献，而且是对每个时间都要求值，考虑设$f(i)$ 表示第$i$ 时间新经过$(x,y)$ 的期望求和，有转移：

$$f(i)=pw_{i}-\sum\limits_{j=1}^{i-1} f(j)\cdot g(i-j,0,0)$$

而$E(x)$ 就是：

$$E(x)=\sum\limits_{i=0}^n f(i) \cdot pw_{n-i}$$

接着考虑$E(x^2)$，我们要处理点对之间的贡献，设$h(i,x,y)$ 表示时间$i$ 内对所有坐标$(a,b)\to (a+x,b+y)$ 的方案数，转移考虑容斥原理，总的方案数是先第一次走到 $(a,b)$，然后任意走到 $(a+x,b+y)$。需要减去经过$(a+x,b+y)\to (a,b) \to (a+x,b+y)$ 的方案和完成目标后在原地打转的方案。总转移方程：

$$h(i,x,y)=\sum\limits_{j=0}^{i-1} f(j)\cdot g(i-j,x,y)-h(j,-x,-y)\cdot g(i-j,x,y)-h(j,x,y)\cdot g(i-j,0,0)$$

因为我们按照顺序计算的贡献，直接求和求出来的是$E(\binom{x}{2})$，那么求答案可以这么写：

$$E(x^2)=E(x)+2\sum\limits h(i,x,y)\cdot pw(n-i)$$

总结：正难则反是一个重要的技巧，通过正难则反，减去的东西就规约到了子问题。

而本题状态定义相当于将等价类定义到了状态中，大大减少了不必要的状态，这是因为它们的总方案易于计算，而容斥的方式是本质相同的，最后的答案也只需要求和，所以可以压缩在一起。这种涉及等价类的状态我们可以学习，这一类题也同样在皮配出现，寻找等价类是就是找它们的共同点。

P1721 [NOI2016] 国王饮水记

直接 DP 发现不会转移难泵了。

考虑发掘性质：

• $h_{i}< h_{1}$ 不会贡献答案，显然可以去掉不会影响答案。
• 一个水站最多会被除$h_{1}$ 之外合并一次。
• 若操作次数管够，一定是将$h$ 从小到大，一个一个和$h_{1}$ 进行操作。

我们发现第三个性质很 ok 啊，我们考虑给它拓展有拓展次数的情况，那么我们观察样例解释发现他们会通过把一些数取平均数后，然后和$1$ 整体操作。

那么就好说了，我们有一个策略，就是如果有操作次数的情况下，我们将这个$h$ 从小到大，让后我们将它们划分为几段，让后我们一个一个和$1$ 进行操作。这其中要满足段数单调不增。

现在可以 DP 了，设$f(i,j)$ 表示进行到前$i$ 个，划分了$j$ 段，$h_{1}$ 的最大取值。转移枚举下一个划段：

$$f(i,j)\leftarrow \dfrac{f(k,j-1)+\sum\limits_{p=k+1}^i h_{p}}{i-k+1}$$

转移是$O(n^3 p)$，可以通过前缀和优化，设$sumh_{i}=\sum\limits_{i=1}^i h_{i}$，有：

$$f(i,j)\leftarrow \dfrac{f(k,j-1)+sumh_{i}-sumh_k}{i-k+1}$$

时间复杂度$O(n^3)$，考虑优化，这个分式有点奇怪，考虑变形：

$$f(i,j)\leftarrow \dfrac{sumh_{i}-(sumh_{k}-f(k,j-1))}{i-(k-1)}$$

这是一个不是很典型斜率优化，考虑把转移的含义看成最大化斜率。具体的，平面有一堆$(i-1,s_{i}-f(i,j-1))$ 的转移点，要求$(i,s_{i})$ 到选定转移点连成直线的斜率最大。

我们要维护的是转移点的下凸包，可以用单调队列优化至$O(n^2p)$。

最后的分数需要发现非$1$ 的段只有$O(\log n)$ 个，也就是说我们只需要 dp 大概 14 层即可，后面的的拿单个补齐，层数很少的时候 dp 可以直接用 double，让后得到转移点之后用高精度计算即可，时间复杂度$O(n\log n+np)$。

总结：这种是不常见的斜率优化式子，是要求我们变形出斜率的形式，来去维护凸包。

2025牛客多校第一场（模拟赛T2）

分析性质，发现这个切割可以看作一个树形结构，将区间树选择一个地方劈开，让后会分裂为左右子树，而左右子树也可以继续递归直到叶子，而叶子我们是直到答案的就是 0。启示我们进行类似于区间 dp 的操作

设$f(l,r)$ 表示将$[l,r]$ 整段切开的最小代价，设$g(l,r)$ 表示$[l,r]$ 切第一刀的决策点在哪里，转移枚举分界点通过$g(l,r)$ 转移满足限制即可，时间复杂度$O(n^3)$。

很遗憾，这是错的，只有 20 分，为什么？因为我们的状态无法满足题目的限制，放到树上相当于就是父节点的不平衡值大于等于子区间所有不平衡值，但是我们 DP 在计算过程中低代价方案可能被剪掉（即本来有代价更大，但是满足限制但是因为 DP 没有记录导致错误），导致有解的方案输出无解。

故设$f(l,r,k)$ 表示$[l,r]$ 但是分割点在$k$ 的阈值$D$ 和最小代价（二元组）。

转移考虑先枚举切点$k$，左右和$L=sum(l,k),R=sum(k+1,r)$，那么不平衡度就是$D=|L-R|$，代价就是$cost=\min(L,R)\cdot \lceil \log_{2}D\rceil$。

转移即为：

$$f(l,r)\leftarrow (D,\text{ask}\{f(l,k),D\}+\text{ask}\{f(k+1,r),D\}+C)$$

其中$\text{ask}$ 表示一个函数，支持查询区间$[l,r]$ 能在最大不平衡$\le D$ 的条件下实现的最小总代价。可以通过前缀$\min$ 加二分实现。

时间复杂度$O(n^3 \log n)$。

总结：

在设计状态的时候，要考虑情况完全，要保证设计的状态能够导出整个子问题。本题错点不再子问题寻找，而是在于状态的设计出了锅。以后 DP 转移一定要列全，跟着 OI BIG Trick 的步骤一步一步做。

P11085 [ROI 2019] 学生座位

考虑发掘性质：

• 将学生按升高排序之后相邻两个配对最优。

• 把课桌升序排序之后按顺序分给学生最优。

性质 2 是很有用的，但是后面再说。

既然这么说了，我们可以把$m$ 组同学相邻同学绑到一起，一共一组最多$O(n)$ 块。而计算课桌的代价的时候因为课桌升序排序之后按顺序分给学生最优，可以通过单调性双指针，时间复杂度$O(nm+mk)$，无法通过。

我们没有很好的利用单调性，第二个代表决策单调性，每次求第$mid$ 的最优匹配点，然后左右的决策点范围是$[ql,mid],[mid,qr]$，用 CDQ 分治容易有$O((k+nm)\log m)$。

CF1562E Rescue Niwen!

2500* 没做出来。

考虑最长上升子序列有什么性质，遥想当年 DIV3 模拟赛 LIS 的一个解法：维护末尾元素的转移。这里我们同样的，维护结尾子串的转移。但是还不能进行 DP，考虑发掘性质：

• 对于子串，字典序大小有$s[i,j]<s[i,j+1]$。也就是说一旦选取$s[i,j]$，那么$s[i,j+1],s[i,j+2],\dots,s[i,n]$ 一定会被选。证明考虑反证法，我证明了 5 万年。

这个性质很有用，考虑直接对末尾进行 DP，设$f(i)$ 表示结尾为$[i,n]$ 的子串的最长上升子序列，转移考虑枚举新后缀$j$，求它们之间的最长公共前缀$lcp$，只要$s_{i+lcp}>s_{j+lcp}$ 即可转移，转移方程如下：

$$f_{i}=(n-i+1)+\max_{1\le j <i} \{ f_{j}-\text{lcp}(i,j) \}$$

时间复杂度$O(n^2)$。

总结：

考虑有效状态又多了一种思路：只求出跟答案相关的 dp 值即可，只用于转移的 dp 值可以考虑其性质。

CF708E Student’s Camp

这个题好像每太那么多的性质，那么直接 DP 发掘性质吧。设$f(i,j,l,r)$ 表示$i$ 天过去了，第$j$ 行，$[l,r]$ 还在的概率。但是我们发现我们都钦定第$j$ 行谁还联通，不如大胆一点，直接把天数去掉！设$f(i,l,r)$ 表示第$i$ 行，$[l,r]$ 还在并且前$i-1$ 行还联通的概率。

然后考虑转移，发现转移有些困难，但是在这之前我们需要预处理一个玩意$g_{i}$ 表示一行掉了$i$ 个格子的概率，这个玩意可以$O(1)$ 做：

$$g_{i}=\binom{k}{i}p^i (1-p)^{k-i}$$

然后回到主题转移，发现转移时真的困难，因为转移的时候我们需要保证$i-1$ 连通，正难则反，考虑容斥减去不连通的方案数。

$$f(i,l,r)=g_{l-1}\cdot g_{m-r} \cdot (\sum\limits_{l'\le r'}f(i-1,l',r')-\sum\limits_{l'\le r' < l}f(i-1,l',r')-\sum\limits_{r<l'\le r'}f(i-1,l',r'))$$

不难后面的东西可以前缀和优化，令：

$$\begin{aligned}F(i)&=\sum\limits_{l'\le r'}f(i-1,l',r')\\L(i,x)&=\sum_{l'\leq r'<x}f(i-1,l',r')\\R(i,x)&=\sum_{x<l'\leq r'} f(i-1,l',r') \end{aligned}$$

优化即可时间复杂度$O(n^3)$，然后就不会优化了。

事实上当然是可以的啦，考虑后面的求和式子，一个关键观察式子只和求和有关而没有其他的式子，考虑以这个突破口，考虑到答案只需要整体求和，我们可以把状态也定义成和式。设$S(i,r)=\sum\limits_{l\le r}f(i,l,r)$，考虑写出这个和式的转移：

$$S(i,r)=\sum\limits_{l}g_{l-1}g_{m-r}\cdot (F(i-1)-L(i-1,l)-R(i-1,r))$$

把$r$ 有关的部分提出来有：

$$S(i,r)=g_{m-r}\cdot\{(F(i-1)-R(i-1,r))\cdot \sum\limits_{l\le r} g_{l-1}-\sum\limits_{l\le r}g_{l-1}\cdot L(i-1,l)\}$$

用前缀和维护$\sum\limits_{l\le r} g_{l-1}$ 和$\sum\limits_{l\le r} g_{l-1} \cdot L(i-1,l)$ 即可，而$R$ 的计算可以用对称性用$L$ 计算，这是因为左右是等价的，所以翻折之后对应的值是相等的。

时间复杂度$O(n^2)$。

总结：

这里给出了 DP 的一种的新的优化方式，如果 DP 式子只和求和有关，我们可以将状态定义为和式来进行计算。

ARC160FCount Sorted Arrays

邦邦卡邦！学会了新的排列双射方式！

一个新的排列双射方式就是将排列$P$ 拆成$n$ 个 0/1 串$C_{1},\dots,C_{n}$，其中$C_{i,j}=[P_{j}\ge i]$，那么$P$ 与$C$ 构成双射。而一个排列合法当且仅当分成的每个 01 序列最后操作完都是有序的。

同时分析题目的操作，因为逆序对数最多是$O(n)$ 个，所以交换最多也只能是$O(n^2)$ 级别的。

我们回到这题，我们考虑让$C_{x,j}$，其中$x$ 从$n,n-1,\dots,1$ 一次下降，每降一次阈值，就恰好有一个位置$i$（值等于当前的$x$）从 0 变成 1。因此得到的 01 串序列是：

• 起点：全 0（可以看作$x=n+1$）
• 每一步把某个坐标从 0 翻到 1
• 终点：全 1（$x=1$)

这正是一条在$\{ 0,1\}^n$ 上 “只增不减” 的单调路径。
并且“哪一个坐标在第$t$ 步被翻到 1”，恰好是“值为第$t$ 大的元素所在的位置”。

故每个排列对应一条唯一的单调路径，双射成功！问题转化为格路计数问题！时间复杂度$O(q2^n)$，同时操作数是$O(n^2)$ 级别的也是可以特判的，只有存在至少一个 01 排序后还有 $p_{u}> P_{v}$​ 时 $(u,v)$ 操作才是有必要的。

更新操作必要性状态即可，时间复杂度$O(n^3 2^n)$。

总结：

计数问题当我们无从下手，我们可以借助一些已有的知识与原命题构成双射。简化问题。

CF1387B2 Village (Maximum)

发现这个就是点之间进行配对，有一个 Trick 就是将点对之间贡献分摊到边的贡献上。我们考虑边的贡献，也即是这条边究竟被经过了多少次，这个次数有一个显然的上界就是$2\times \min(siz_{u},siz_{v})$，其中$siz$ 表示子树大小。

考虑如何构造使得经过次数最大，考虑式子$2\times \min(siz_{u},siz_{v})$ 与取$\min$ 有关，也就是说我们应当尽量让这个$\min$ 大。考虑这个$\min$ 上界是多少，有$siz_{u}+siz_{v}=n$ 不难证明$\min$ 上界就是$\lfloor \dfrac{n}{2}\rfloor$。这个上界什么时候取到，当然就是在树的重心。

考虑以树的重心为根，下面挂的子树大小都不超过$\dfrac{n}{2}$。那么子树里面的点贪心策略一定是跨子树配对，故我们可以将所有节点按照 DFS 序后，第$i$ 个节点配对$\left(i+\dfrac{n}{2}-1\right)\bmod n +1$ 个节点即可在另一个子树配对，时间复杂度$O(n)$。

这道题的一个小 Trick 的就是将点对贡献分摊到边上，同时我们在最大化链的长度的时候要尽量跨子树。同时这个循环移位配对也是很好的思想。