动态规划复习~

The Maximum Prefix *3200

你需要生成一个长度不超过 \(n\) 的数组 \(a\)，其中每个 \(a_{i}\) 的取值为 \(1\) 或 \(-1\)。

你按照如下方式生成该数组：

• 首先，你选择一个整数 \(k\)（\(1\le k \le n\)），决定数组 \(a\) 的长度。
• 然后，对于每个 \(i\)（\(1\le i \le k\)），你以概率 \(p_{i}\) 令 \(a_{i} = 1\)，否则以概率 \(1 - p_{i}\) 令 \(a_{i} = -1\)。

数组生成后，你计算 \(s_{i} = a_{1} + a_{2} + a_{3}+ \ldots + a_{i}\)，特别地，\(s_{0} = 0\)。然后令 \(S = \displaystyle \max_{i=0}^{k}{s_{i}}\)，即 \(S\) 是数组 \(a\) 的最大前缀和。

你会得到 \(n+1\) 个整数 \(h_{0}, h_{1}, \ldots, h_{n}\)。对于最大前缀和为 \(S\) 的数组 \(a\)，其得分为 \(h_{S}\)。现在，对于每个 \(k\)，你需要求出长度为 \(k\) 的数组的期望得分，对 \(10^9+7\) 取模。\(n \le 5000\)。

注意经典题。

前缀和如果正向做不容易同时维护 \(S\) 和当前前缀和。注意倒着做，定义 \(f_{i,j}\) 表示确定了 \(i \sim k\) 的值，当前最大前缀和为 \(j\) 的概率。注意在开头加一个数，容易发现 \(S=j \to S=\max\{0,j \pm 1\}\)，因为前缀和会整体都 \(\pm 1\)，再在前面加一个 \(0\)。

\[f_{i,j}(1-p_{i-1}) \to f_{i-1,\max\{j-1,0\}}\\ f_{i,j}p_{i-1} \to f_{i-1, j+1} \]

但是注意，这里隐含了 \(k\) 的 \(\mathcal O(n)\) 枚举，总复杂度 \(O(n^3)\)，因此，注意这个 dp 是多个起点单个终点，需要改变 dp 方向。

倒过来就好了。考虑 dp 意义，\(g_{i,j}\) 表示确定 \(1 \sim i\) 的值，当前离我期望达到的最大前缀和 \(S\) 还需后面的 \([i+1,k]\) 这一部分最大前缀和为 \(j\) 才可以，得分的期望值。

\[\begin{aligned} g_{i-1,\max\{j-1,0\}}p_i &\to g_{i,j}\\ g_{i-1,j+1}p_i &\to g_{i,j} \end{aligned} \]

First Come First Serve *2697

有 \(N\) 位顾客会光顾某家店，我们将他们编号为 \(1,\ldots,N\)。第 \(i\) 位顾客在时刻 \(A_i\) 进入店内，在时刻 \(B_i\) 离开店铺。该店的排队方式为“先进先出”，即 \(A_i\) 和 \(B_i\) 都是严格递增的。此外，所有的 \(A_i\) 和 \(B_i\) 互不相同。

在店门口有一份顾客可以签名的名单。每位顾客仅能在入店时或离店时，将自己的名字写在名单的末尾一次。请问，最终名单上名字的可能排列方式有多少种？请将答案对 \(998\,244\,353\) 取模后输出。\(N\le 5 \cdot 10^5\)。

一种签名方式的选择序列：如 \(abaa...\)，第 \(i\) 为表示顾客是选择 \(A_i\) 还是 \(B_i\) 时签名。选择序列每个人只有 \(2\) 个选择，考虑从这个角度计数。

一个名字排列所对应多种选择序列，所以套路性的，考虑代表元，容斥掉非代表元的部分。

令代表元为：对应同一名字排列中选择序列尽量多选 \(A_i\) 的那一个。

• 选择 \(a_i\)，系数为 \(1\)。
• 选择 \(b_i\)，不考虑其他情况，系数为 \(1\)。
• 选择 \(b_i\)，但 \(a_i \sim b_i\) 这一段无人签名，系数为 \(-1\)。

定义 \(f_i\) 为决策完 \(1 \sim i\) 位的状态，方案的系数积之和。

\[f_i \gets f_i+2f_{i-1}\\ \forall i:f_p\gets f_p-f_q \]

其中 \(i\) 是对应第三种情况的 \(i\)，\(q=\max\{j|j<i \land b_j<a_i\},p=\min\{j|j>i\land b_i<a_j\}\)，直接维护就可以做到 \(\mathcal O(n)\) 了。

Bow Meow Optimization

有 \(N\) 只编号为 \(1\) 到 \(N\) 的狗，以及 \(M\) 只编号为 \(1\) 到 \(M\) 的猫。现在要将这 \(N+M\) 只动物以任意顺序排成一排。根据排列的方式，每只狗和猫会产生如下的“不满度”：

• 对于第 \(i\) 只狗，设在它左边的猫有 \(x\) 只，右边的猫有 \(y\) 只，则它的不满度为 \(A_i\times|x-y|\)。
• 对于第 \(i\) 只猫，设在它左边的狗有 \(x\) 只，右边的狗有 \(y\) 只，则它的不满度为 \(B_i\times|x-y|\)。

请你求出所有动物不满度总和的最小值。

• \(1\leq N, M \leq 300\)
• \(1\leq A_i, B_i \leq 10^9\)
• 输入均为整数

性质是前 \(\lfloor\frac{m}{2}\rfloor+\lfloor\frac{n}{2}\rfloor\) 中一定有 \(\lfloor\frac{m}{2}\rfloor\) 只猫和 \(\lfloor\frac{n}{2}\rfloor\) 只狗。

将左边多余的猫与右边多余的狗交换调整即可得证。

[CSacademy]Squared Ends，link

将序列划分为 \(k\) 段，每段的价值为 \((A_l-A_r)^2\)，求价值和的最小值。

\(A_i \le 10^6,n \le 10^4,k \le 100\)

\[\begin{aligned} f_{i,j}&=\min _{k < i}\{f_{k,j-1}+A_{k+1}^2+A_i^2-2A_{k+1}A_{i}\}\\ &=\min_{k<i}\{f_{k,j-1}+A_{k+1}^2-2A_{k+1}A_i\}+A_i^2 \end{aligned} \]

李超线段树维护即可做到 \(kn \log n\) 的复杂度。

斜率优化

注意李超线段树是直观的竖线找最高/低交点，但斜率优化最常见的写法并非如此：

若方程 \(f_{i}=\min_{j <i} \{a_{j}+c_jd_i\}+e_i\)，斜率优化是将其看做：

前有若干点 \((x_j,y_j)\)，用斜率 \(d_i\) 去过那个点的直线的最小截距。

对于直线 \(y=kx+b\)，这里逐一替换得到：\(y_j=d_ix_j+b\) 移项：\(y_j-d_ix_j=b\)。

容易得到 \(x_j=-c_j,y_j=a_j\)，方程式写作：\(f_{i}=b+e_i\)，。

然后若斜率 \(d\)，横坐标 \(x\) 分别单调递增，那么可以维护一个下凸壳做到 \(\mathcal O(n)\) 斜优。

Yet Another Partition Problem *3000

给定数组 \(a_1,a_2 ⋯a_n\)，你需要将它划分成 \(k\) 段（每个元素在且仅在一段中），某段 \(a_l,a_{l+1} ⋯a_r\) 的权值为 \((r−l+1) \times \max\limits_{i=l}^r{a_i}\)，整个划分的权值是每段权值之和。求最小划分权值。

\(n \le 2×10^4 ，k \le 100\)。

定义暴力 dp，\(f_{i,j}\) 表示将 \([1, j]\) 划分为 \(i\) 段的最小代价。

转移：

\[f_{i,j}=\min_{k<j}\{f_{i-1,k}+c(k+1,j)\} \]

观察代价函数 \(c(l,r)=(r-l+1)\displaystyle\max_{l\le i \le r} a_i\)，发现 \(\max\) 并不是一个友好的东西。

单独考虑每一层转移，即 \(f_{i-1} \to f_i\)：

考虑分治，处理 \([l,m]\) 到 \([m+1,r]\) 的转移，然后递归处理内部转移。

想想这样有什么好处，分治后从 \(m\) 两边开始可以 \(\mathcal O(n)\) （每层而言）处理出 \(\max\)，然后将 \(\displaystyle\max_{l \le i \le r}\) 拆成 \(l \le i \le m\) 一段和 \(m < i \le r\) 一段的 \(\max\)。令 \(lm_i\) 为左边的后缀 \(\max\)，\(rm_i\) 为右边的前缀 \(\max\)。

然后就可以将转移写作：

\[f_{i,j} \gets \min\{f_{i-1,k}+(j-k)\max\{lm_{k+1},rm_j\}\} \]

这样就比较方便分讨：

• \(lm_{k+1} \le rm_{j}\)：转化为斜优形式就是：

  \[f_{i,j} \gets \min \{f_{i-1,k}-k\times rm_{j}\}+j \times rm_j \]

• \(lm_{k+1} > rm_{j}\)：转化为斜优形式就是：

  \[f_{i,j} \gets \min \{(f_{i-1,k}-k\times lm_{k+1})+j\times lm_{k+1}\} \]

两者均可以使用斜率优化，所以只需考虑将 \(lm_{k+1}\) 与 \(rm_{j}\) 大小关系放到 dp 中，双指针即可。

[AGC039E] Pairing Points *3430

在一个圆上有 \(2 N\) 个点，其中有一些点对之间有连线，给出了连线的邻接矩阵 \(A_{i, j}\)。

并且保证不存在三线共点的情况。

你需要选择其中 \(N\) 条线保留下来，使得每个点恰好连一条线，并且这 \(N\) 条线画出来后构成一棵树。

请求出不同的连线方案的数量。

• \(1 \le N \le 20\)。

非常 Educational 的一道题！

\(N \le 20\) 容易想到状压，但发现其中似乎没有特别直观的需要进行压缩的集合状态。

因此先找性质。首先这道题不合法的情况也不太好统计，容斥就会显出劣势，直接对着树这个良好的结构 DP 是一个很好的想法。

首先树呈现出一个递归子结构，与 DP 划分子问题的形式十分相像，具体而言，就是：

为刻画这个划分子问题的形式，回归到 DP 定义，发现子问题主要需要记录 \(2\) 个状态：

• 需要跨越哪一根线，记录需跨越的点 \(m\)，由图可知，\(m\) 点需要向外连。
• 在哪一个区间内配对，记录该区间的 \(l,r\)

首先第一步划分直接特殊处理，使 DP 过程处在一个非环的结构上。

定义 \(f(l,m,r)\)，表示 \([l,m)\cup (m,r]\) 这段区间内配对，且至少有 \(1\) 个区间跨越 \(m\) 的方案数。

由图就容易得出转移了：

• 枚举一个代表，使区间划分成 \(3\) 个子问题，取跨越 \(m\) 的线段的端点中，最靠近 \(l\) 和最靠近 \(r\) 的点，记作 \(p,q\)。
• 枚举 \([l,x]\) 和 \([y,r]\) 两部分，表示 \([l,m)\) 区间中，\(x\) 为一个断点；\((m,r]\) 区间中，\(y\) 为一个断点，这样就保证不成环。
• \(f(l,m,r)=\displaystyle\sum _{p,q,x,y}f(l,p,x)\times f(y,q,r)\times f(x+1,m,y-1)\)

使用记忆化搜索，剪去无用状态即可快速转移。\(\mathcal O(n^3 \cdot n^4)=\mathcal O(\dfrac{n^7}{一个比较大的数})=\mathcal O(飞快)\)。

这就启示我们，\(\bf 20\) 也不一定是 \(\bf 2^n\) 级别算法。

Shrinking Tree *2900(?)

对于一棵有 \(n\) 个节点的树 \(T\) 。当 \(T\) 的节点数多于一个时，反复执行以下操作：

• 等概率地选取 \(T\) 中的一条边。

• 收缩选取的边：即合并这条边连接的两个点 \(u\) 和 \(v\) 。得到的新点的编号等概率地从 \(u\) 和 \(v\) 中选取一个。

当这个过程结束时， \(T\) 只剩一个节点了，它的编号可能是 \(1,\ldots,n\) 中的任意一个数。对于每个编号，请输出最终得到这个编号的概率。

\(1\le n\le 50\)。

黑得发黑。

发现选边序列确定后的答案也不太显然，先尝试做一下。

令第 \(i\) 次选择编号为 \(p_i\) 的边。容易感受到，缩合点的编号当作一个集合，那么，点 \(i\) 所属集合编号为 \(i\) 的概率在这个集合每次扩张时都会减半，所以编号为 \(i\) 的概率即为：\(2^{-c}\)，\(c\) 为 \(i\) 所处集合扩张次数。直接用并查集就可以 \(\mathcal O(n^2)\) 做。

考虑原问题，\(n\) 较小，考虑直接枚举最终节点编号 \(r\)，不妨以 \(r\) 为根。树形结构，找性质进行树形 DP，先统计所有选边序列的概率之和。

由于是求包含 \(r\) 的集合的扩张次数，那么子树的根 \(u\) 在还没有被缩到 \(r\) 之前是对答案毫无贡献的。

而此处又并不需要具体知道 \(u\) 外面怎么缩的，只需要知道 \(u\) 在哪一次操作被缩到 \(r\) 节点上的。这样做可以消除后效性，令 \(f_{i,j}\) 表示 \(i\) 节点在删掉子树内第 \(j\) 条边后（且必须在第 \(j+1\) 条边前(不包含)，即在这段时间区间内）和 \(r\) 节点进行交合之事，\(i\) 子树内对 \(r\) 答案有产生的扩张贡献之和。（属于代价提前预知的方法，此处扩张贡献即为扩张次数 \(c\) 对应的 \(2^{-c}\) 之和）

转移考虑枚举 \(i,j\) 表示 \(u\) 子树（在 \(v\) 之前的 \(u\) 子树）内删完 \(i\) 边后（意义理解同上），\(v\) 子树内删完 \(j\) 边后，因此合并后的 \(u\) 子树会在 \(i+j\) 边删掉后，\(i+j+1\) 边删掉前缩并到根上去。前半部分（\(u\) 子树内删完 \(i\) 边后）的代价显然为 \(f_{u,i}\)，而由于后半部分（\(v\) 子树内删完 \(j\) 边后）由 \(f\) 直接得出的结果为 \(v\) 缩并在 \(r\) 上的时间而非 \(u\) 缩并在 \(r\) 的时间，需要单独计算。这俩合并流程还存在多种方案，因此需要考虑一下。总的来说需要考虑的转移系数有：

• \(u\) 子树内删完第 \(i\) 条边后缩并到 \(r\) 的代价。

  见上，即为 \(f_{u,i}\)。

• \(v\) 子树内删完第 \(j\) 条边后 \(\mathbf u\) 缩并到 \(r\) 的代价。

  令 \(g_{v,i}\) 表示【子树 \(v\) + 父节点 \(u\)】删完第 \(i\) 条边后，\(u\) 缩合到 \(r\) 的代价。

  转移，枚举删 \((u,v)\) 的时间 \(k\)：

  • \(k<i\)，\(g_{v,i}\gets f_{v,k}\)（此处，\(k\) 只能为 \(i-1\)）
  • \(k\ge i\)，将会对扩张次数产生影响，\(g_{v,i} \gets \frac{1}{2}f_{v,k}\)。

• 合并方法的不同导致被转移划分为同一类的不同方案的总数。

  首先 \(i,j\) 这几条在 \(u\) 缩并之前的钦定边可以任意组合，为 \(\dbinom{i+j}{i}\)。

  然后剩余边的顺序任意排，也可以组合一下：\(\dbinom{sz_u+sz_v-1-(i+j)}{sz_v-j}\)。

至此😥，终于得到转移式，\(f'_u\) 为合并后的答案：

\[f'_{u,i+j} \gets f_{u,i}g_{v,j}\binom{i+j}{i}\binom{sz_u+sz_v-1-i-j}{sz_v-j}\\ \]

所有子树合并后进行 \(g\) 的转移：

\[g_{u,i} = f_{u,i-1}+\frac{1}{2}\sum_{k \ge i} f_{u,k} \]

第二个下标与 \(sz\) 有关，可以优化复杂度到 \(\mathcal O(n^2)\)。

总的时间复杂度为 \(\mathcal O(n^3)\)。

Sum on Codeforces *2800

给定 \(n\) 个非递减的非负整数数组。

Vasya 重复进行 \(k\) 次如下操作：

• 选择一个非空数组。
• 将所选数组的第一个元素放进口袋。
• 从所选数组中移除第一个元素。

Vasya 想要最大化他口袋中元素的和。

\(n,k \le 3000,\sum |a_i| \le 1\cdot 10^6\)。

观察是如果选了一个数组的数字，就尽量把这个数组选空，这样做是一个最优方案。

即证最多存在 \(1\) 个非空且被选了的数组，若有两个，设它们最后一个选的元素分别为 \(x,y\)

不妨设 \(x\le y\)，那么选了 \(y\) 之后肯定选 \(y\) 的下一个不劣，进入循环，直到把 \(y\) 这一个数组选空。

所以枚举没选满的数组 \(i\)，剩下的等价于做一个 0/1 背包。

问题转变为，对于每个 \(i\) 求出 \([1,i)\cup (i,n]\) 的背包。复杂度是 \(\mathcal O(n^2k)\)。可以想到一个基于前后缀背包合并的做法 \(\mathcal O(nk^2)\) 解决问题，但是没有本质区别。

注意到单次插入的复杂度为 \(\mathcal O(k)\)，但合并却达到了 \(\mathcal O(k^2)\)。

背包的常见套路考虑如何将合并转为插入，考虑分治。

• 将 \([l,m]\) 的部分依次插入背包，递归进入 \((m,r]\)。
• 退出递归后，将背包还原（到进入当前递归层时），将 \((m,r]\) 的部分插入背包，递归进入 \([l,m]\)。

于是在分治叶子处，背包即为 \([1,i)\cup(i,n]\)。

Three Permutations *2893

给定长为 \(n\) 的排列 \(p,q\)，求满足所有 \(r_i \neq p_i,q_i\) 的排列 \(r\) 总数。

\(n \leq 3 \cdot 10^3\)

可以先把 \(q\) 变成 \(1,2,\dots,n\)。

那么问题就变成错排 + 第 \(i\) 位不能填 \(i\) 的限制。容斥，设钦定 \(k\) 位满足 \(r_i=p_i \lor r_i=i\) 的方案数为 \(f(k)\)，答案即为 \(\displaystyle \sum _{k=0}^n (-1)^k(n-k)!f(k)\)

现在每个钦定不满足条件的 \(r_i\) 有两个选择，套路性的，连边 \(i \to p_i\)，单独考虑每个环，断环 DP 是很容易的。最后再用一个背包合并所有环的答案即可求出 \(f(k)\)。

Mowing Mischief P

给定 \(n,T\) 和 \(n\) 朵花的坐标 \((x_i,y_i)\)，在一个 \(T \times T\) 的网格上，两只奶牛从 \((0,0)\) 出发，到 \((T,T)\)，但是牠们只能向右或向上走，且两牛速度相同，求牠们的连线扫过的面积最大值。

额外限制：可以选定一个花的集合，强制要求两只奶牛的路径必须经过这个集合的每个点。

\(n \le 2 \cdot 10^5, 1 \le T \le 10^6\)，且 \(1 \le x_i,y_i < T\)，保证 \(x_i\) 互不相同，\(y_i\) 互不相同。

容易发现确定集合后答案是显而易见的，就是将相邻两个点连线作为对角线的若干矩形面积之和。实际上，答案可以表示为：

\[\sum _{i=2}^{|S|}(x_{S_i}-x_{S_{i-1}})\times (y_{S_i}-y_{S_{i-1}}) \]

按 \(x\) 排序，令 \(f_{i}\) 表示在 \([1,i]\) 中选花，强制选择第 \(i\) 朵花的答案最小值（尽量让 \(|S|\) 更大），容易给出状态转移：

\[f_{i} = \min_{j < i \land y_j < y_i \land j\to i} \{f_{j}+(x_i-x_j)(y_i-y_j)\} \]

\(j \to i\) 表示 \(j\) 可以作为以 \(i\) 结尾的最长上升子序列的上一个节点。设以 \(i\) 结尾的最长上升子序列的长度为 \(c_i\)，\(j\to i \Leftrightarrow c_j=c_i-1\)。

按照 \(c_i\) 分层，同层节点有这样的性质：只能一次转移到下一层节点；若 \(x_i<x_j\)，则 \(y_i > y_j\)，否则会分到不同层。\(x\) 排序后，其实每一层 \(y\) 也是排好序的，只是单调递减而已。

这里单调性的暗示非常明显，画个图可以知道，\(i<j\) 时，如果 \(k\) 正在决策选 \(i\) 还是 \(j\)(当然，\(c_k-1=c_i=c_j\)，且 \(i,j\) 都能转移到 \(k\))，随着 \(k\) 增大（\(x_k\) 增大，\(y_k\) 减小），\(k\) 与 \(i\) 围成的面积逐渐增大，\(k\) 与 \(j\) 围成的面积逐渐减小（减去公共部分后）。

所以当 \(i < j\) 时，随 \(k\) 增大若决策选了 \(i\) 就不会再选 \(j\) 了。总结一下，决策单调性呈现的是：同层决策点单调递减。然而，加上 \(y_i < y_k\) 的条件后，根据 \(y\) 的单调性，可以作为 \(k\) 的决策点的 \(i\) 是一个连续区间，但这个连续区间却是在随着 \(k\) 的增大而不断右移的。

考虑能作为每个点的决策点的位置在输入时就已经确定，于是就可以利用线段树分治把决策区间砍成 \(\mathcal O(\log n)\) 个，在线段树节点上进行分治优化决策单调性，对于第 \(i\) 层单次复杂度就是 \(\mathcal O(\sum[c_j=i] \log^2 n)\)，然后问题就在 $\mathcal O(n \log ^2n) $ 内解决。

直接分治优化决策单调性的题目需要满足每个状态共享同一个转移区间或转移区间的移动方向与决策单调性方向相同，在本题中不适用，因此通过线段树分治消耗一只 \(\log\) 使节点上的状态转移共享同一转移区间，就可以用决策单调性优化。

262144 Revisited P

定义一个数列的贡献为：每次选择数列中 \(2\) 个相邻的数 \(a,b\)，删去 \(a,b\) 并在原位置插入一个 \(\max\{a,b\}+1\)，求当这个数列只剩一个数时这个数的最小值。

给定数组 \(a\)，求其所有子数列的贡献之和。

\(1 \le n \le 262,144, 1 \le a_i \le 10^6\)。

这道题提供了一种区间 DP 的优化思路。也许，区间 DP 没前途，但是或许可以改变它的状态定义？

区间 DP 自然是容易看出的，\(f_{l,r}\) 表示 \(a[l,r]\) 的贡献，\(\mathcal O(n^3)\)。

如果拿这个定义，不论如何优化最多只能抵达 \(\mathcal O(n^2)\)。观察题目的显然性质：

• 区间越长，贡献越大：\(\forall [l,r] \subseteq [p, q],f_{l,r} \le f_{p,q}\)。真是一个美妙的单调性！
• 贡献的上界不超过 \(O(n+A)\)，\(n+A\) 是用最垃圾的每次与最大值合并的方法合出来的（实际上 \(O(\log n +A)\) 是真实上界，分治合并即可）

答案上界小，贡献具有单调性，重新设计 \(g_{i,j}\) 表示使得 \(f_{l,i} \le j\) 的 \(l\) 最小值。

转移：

\[g_{i,j}=\begin{cases} i&a_i = j\\ g_{g_{i,j-1}-1,j-1} & a_i \neq j \end{cases} \]

现在外层枚举 \(j\)，内层维护 \(g_{i,j}\) 的对应值，容易发现对应值因为 \(g\) 的单调性所以呈现为若干区间，做区间赋值即可。使用线段树二分实现。