动态规划

各类动态规划。真的不会 DP 啊 qaq。

[NOI2019] 回家路线

给定一张有向图，边有 两种属性（），令 ，求一条从 到 的路径 使得

最小。

披着图论外衣的 题。

总时间对答案的贡献可以最后枚举边计算。

设 表示走完第 条边后的最小代价，那么枚举上一条边，则有

展开，忽略 。

斜率优化标准形式。可以按 排序使得斜率单调不降，使用单调队列维护。

再考虑限制。

• ： 对于每一个 单独维护即可。
• ：由于已经按 排序，因此处理到 时所有 的 已经全部处理完毕。可以在处理完每条边的 值后按 压入等待队列，处理到 时将所有 依次压入单调队列。

[NOI2020] 美食家

简要题意就不放了。

初步想法是，设 表示第 天到城市 能获得的最大价值，则

由于 很大，考虑使用矩阵优化复杂度。

点权很麻烦，将点权转化为边权。

先丢掉第二维和后面一坨额外价值，将边用邻接矩阵 存储。则有

本题中定义矩阵乘法为 矩乘。

注意到矩阵乘法一次只能转移一步，并且 。考虑拆点，把点 拆成形如 的链。再结合点权到边权的转化，可以将形如 的边转化为 （所有边代价均为 ）。

对于没有额外价值的转移，我们可以直接矩阵快速幂；而对于额外价值，单点加即可。

发现简单的矩阵快速幂复杂度不够优秀，可以预处理出 。

时间复杂度 。

引理

语文太差讲不清楚。OI Wiki。

【模板】LGV 引理

比较直接的 引理应用。

注意到 以及 ，因此只要路径不相交就必然满足条件。所有路径权值均为 。

网格图上 到 、只能向右或向下的路径数即为 。

[NOI2021] 路径交点

每个起点所对应终点形成一个排列，容易发现路径交点个数与排列逆序对数同奇偶。

题目要求交点为偶数的方案数减去奇数的方案数，因此两种路径对答案的贡献分别是 和 。

发现系数恰好对应 引理中的系数。对于每个起点广搜出到每个终点的路径方案数，矩阵求行列式即可。

[NOI2020] 命运

树形 。

发现给出的限制很特别：一定是祖先到子孙节点的限制。为了方便，下面记深度较浅的点为起点，另一个点为终点。

注意到一个性质：处理完 子树内的点后，对于所有跨过点 （即两端分别在 子树内外）且未被满足的限制，只有起点深度最大的限制是有用的。

证明很简单。深度最大的限制被满足后其他限制自然被满足。不妨设根节点深度为 。

设计状态 表示处理完 子树内，深度最大的未被满足的限制深度为 （不存在即为 ）的方案数。答案即为 。不合法状态方案数为 。

考虑转移。将 合并到父亲 上，枚举 到 的边是否染色，有

记 ，则有

得到了 的解法。

发现每个节点初始状态只有一种，又是二维状态、自底向上合并的形式，使用线段树合并优化复杂度。

合并的时候先合并左二子再合并右儿子，更新的时候维护一下前缀和即可。

注意 第二维下标从 开始。

[省选联考 2021 A/B 卷] 滚榜

数据范围一眼状压。

令 表示已经滚榜的队伍集合为 ，上一个滚榜的队伍为 且封榜后过了 题，封榜后一共过了 题的方案数。

直接做是 的，考虑优化。

发现只需要排名的方案数，不需要真正分配 。尝试最小化 。

对于队伍 与前一个队伍 ，有

那么，对于一个确定的滚榜顺序 ，有

于是可以设 表示已经滚榜的队伍集合为 ，上一个队伍为 且总代价为 的方案数。直接转移即可。

时间复杂度 。

CF908D New Year and Arbitrary Arrangement

不会。看 sol。

设 表示有 个 和 个子序列 结束时子序列 期望出现次数。

转移有

对于 ，再来一个 后过程结束。

可以算得此时的期望长度为 。参考证明。

注意答案为 ， 会更新自己且开头的一串 没有意义。

CF908E New Year and Entity Enumeration

不会。看 sol。

先不考虑限制，尝试判定集合 是否满足条件。

设 为 中所有第 位为 的数的 和。由定义得，。

若 且 不含 ，那么按定义有 ，而 含 不含 ，与 定义矛盾。

因此，。

原问题相当于将 划分成若干集合的方案数，即为 数。

要求 相当于限定了某些 不相等。对于每个连通块求出答案再相乘即可。

CF1083D The Fair Nut’s getting crazy

*3500。（心虚）

枚举相交区间计算贡献。记 为 上一次出现的位置（不存在则为 ）， 同理。

令 ，则答案即为
$$
\sum_{i=1}^n\sum_{j=i}^n[pre(i,j)<i]j<suf(i,j)(suf(i,j)-j)
$$
显然，随着 递增，最右侧有效右端点单调不降。于是可以双指针维护 。

删除元素相对麻烦，考虑倒序枚举左端点，动态维护 和 。

当加入 时，。

注意到 和 具有单调性，可以二分或单调栈求出最右侧的 使得 ，然后区间赋值。 同理。

接下来考虑答案。固定左端点 ，记最大有效右端点为 ，展开。

线段树维护 ，区间推平即可。

难度集中在代码难度。

还有为什么一场连着两个线段树啊。（