区间 DP
by Heldivis & Lydic & zhujiangyuan
A - CF1509C The Sports Festival by zhujiangyuan
发现 \(d_i\) 一定是单调不降的，所以我们尽可能保证每一步都最小。
将 \(a_i\) 排序，如果当前选出了 \(i\) 个数，一定是在排过序后的数组中连续的一段。
设 \(dp_{l,r}\) 表示选出的区间左端点为 \(l\)，右端点为 \(r\) 时的答案。则最终答案为 \(dp_{1,n}\)。
对于 \(1\le i\le n\)，钦定 \(i\) 为选出的第一项，则 \(dp_{i,i}=0\)。转移：\(dp_{l,r}=\min(dp_{l+1,r},dp_{l,r-1})+a_r-a_l\)。
这样做复杂度是 \(O(n^3)\) 的。
发现可以从外向内转移，也就是倒着选，\(dp_{l,r}\) 为当前选的数 \(\in[1,l]\cap [r,n]\) 时的答案。初始：\(dp_{1,n} = a_n - a_1\)。
转移：\(dp_{l,r}=\min(dp_{l-1,r},dp_{l,r+1})+a_r-a_l\)。
答案：\(\min\limits_{i=1}^ndp_{i,i}\)。
1 | sort (a + 1, a + n + 1); |
B - CF1728D Letter Picking by Heldivis
区间 DP - 平方复杂度
考虑一个区间 \(l\sim r\)：
先手必胜条件：
先手选 \(l\)
必胜条件是后手不管选 \(l+1\) 还是 \(r\)，都是先手获胜。
先手选 \(r\)
必胜条件是后手不管选 \(l\) 还是 \(r-1\)，都是先手获胜。
平局条件：
先手选 \(l\)
必胜条件是后手不管选 \(l+1\) 还是 \(r\)，都是平局。
先手选 \(r\)
必胜条件是后手不管选 \(l\) 还是 \(r-1\)，都是平局。
1 | int Fn(int l, int r) { |
推性质 - 线性复杂度
发现先手必不败。因为只剩最后两个时，只要先取走不大的一个，那么要么平局，要么先手赢。
然后发现，回文、两两重复或回文套两两重复时平局，其余先手胜。
1 | scanf("%s", s + 1), l = 1, r = strlen(s + 1); |
C - CF1666J Job Lookup by Heldivis
其任意一个节点的左子树内所有节点编号都小于它，右子树内所有节点编号都大于它。所以一个区间是一个完整的子树。
考虑枚举一个区间的根 \(k\)，每次转移把路径的贡献拆开，加上左子树到非左子树的贡献、右子树到非右子树的贡献，这两部分在 \(c\) 矩阵上是一个矩形，前缀和维护即可。方案在转移时记录区间的根，最后递归求解即可。
转移方程： \[ \operatorname{C}(l,r,x,y)=\sum_{i=l}^r\sum_{j=x}^yc_{i,j} \] \[ X = \operatorname{C}(l, k - 1, 1, l - 1) + \operatorname{C}(l, k - 1, k, n) + \operatorname{C}(k + 1, r, 1, k) + \operatorname{C}(k + 1, r, r + 1, n) \] \[ f(l,r) \gets \min_{k=l}^{r}\{f(l,k-1) + f(k+1,r) + X\} \]
1 | ll Calc(int sx, int fx, int sy, int fy) { |
D - [USACO04OPEN] Turning in Homework G by zhujiangyuan
因为交作业不需要时间，所以交一个区间的作业的时候，一定是先交左端点或者先交右端点。
设 \(dp_{l,r,0/1}\) 为还有 \([l,r]\) 的作业没交，当前在 \(l/r\) 时的答案。
初始：\(dp_{1,n,0}=\max(x_1,t_1)\)，\(dp_{1,n,1}=\max(x_n,t_n)\)。
转移：从相邻区间的两个状态转移而来。
\[ dp_{i,j,0}=\max\{t_i,\min\{dp_{i-1,j,0}+x_i-x_{i-1},dp_{i,j+1,1}+x_{j+1}-x_i\}\} \]
\[ dp_{i,j,1}=\max\{t_j,\min\{dp_{i-1,j,0}+x_j-x_{i-1},dp_{i,j+1,1}+x_{j+1}-x_j\}\} \]
答案为 \(\min\limits_{i=1}^n\{|b-x_i|+\min\{dp_{i,i,0},dp_{i,i,1}\}\}\)。
时间复杂度 \(\mathcal O(n^2)\)。
1 | sort (a + 1, a + n + 1, [] (Node a, Node b) { return a.x < b.x; }); |
E - [CERC2014] Outer space invaders by Heldivis
考虑如果对一个人进行 DP，发现由于左右端点不固定，不很好转移，考虑对时间 DP。时间显然可以离散化到 \(O(n)\)。
设 \(f(l,r)\) 表示消灭出现时间被 \(l\sim r\) 时间完全包含 的敌人的最小代价，考虑转移：
枚举对距离最大的敌人的攻击时间 \(k\)，此时所有时间区间包含 \(k\) 的敌人都消灭了，还剩下 完全被 \(l\sim k-1\) 和 \(k + 1\sim r\) 时间完全包含的敌人。由 DP 的含义得到就是 \(f(l, k - 1) + f(k + 1, r)\)。
令 \(p\) 为区间内距离最大的敌人，则转移式：
\[ f(l,r)\gets\max_{k=l_p}^{r_p}\{f(l,k-1)+f(k + 1, r) + d_p\} \]
如果区间不完全包含某个敌人 DP 值为 \(0\)；答案为消灭所有敌人，即被整个时间包含的敌人 \(f(1,w)\)，\(w\) 时总时间。
1 | for (int len = 1; len <= w; ++len) { |
F - [USACO17JAN] Subsequence Reversal P by Lydic
根据数据范围，不难想到 DP 状态应该是 \(n^4\) 级别的。
先考虑当没有反转区间的操作时如何转移。
设 \(dp_{l,r,L,R}\) 表示当前区间为 \(l\sim r\)，值域 \(\in [L,R]\) 时的答案。转移时枚举四个维度，可以从 \(dp_{l,r,L,R-1},dp_{l,r,L+1,R},dp_{l+1,r,L,R},dp_{l,r-1,L,R}\) 转移过来。
加上翻转操作后，我们思考其本质。翻转一个子序列可以理解为交换某几对数字的位置，这样的话相当于如果 \(a_l=R\) 或者 \(a_r=L\) 的话，我们可以通过翻转 \(l\sim r\) 中的任意一个包含 \(l,r\) 的子序列来满足条件，即 \(dp_{l,r,L,R}=dp_{l+1,r-1,L,R}+[a_l=R]+[a_r=L]\)。
由于区间 DP 按照区间从小到大的顺序，故可以保证这样的翻转满足题目条件，所以这道题就结束了。
1 | cin >> n; |
G - [春季测试 2023] 圣诞树 by Heldivis
考虑对于：
1 | A B |
这样的节点，一定不会是 \(ADBC\) 这样的路径，因为 \(AD\gt CD,BC\gt AB\)，那么 \(AD+DB+BC\gt CD+DB+BA\)，不如 \(ABDC\) 更优，即线不会有交叉。
考虑设 \(f(l,r,0/1)\) 表示从区间 \(l\sim r\) 的左 \(/\) 右端点，走完区间内的最小代价。把原序列从 \(k\) 断开，改为数值上形如 \(\lor\) 的一个长为 \(n-1\) 的序列。则一定是左边选若干个、然后右边选若干个这样，单独看两边，每次选择时高度单调不升。
答案为 \(\min\{f(1,n-1,0)+\operatorname{dis}(1,n),f(1,n-1,1)+\operatorname{dis}(n-1,n)\}\)，其中 \(\operatorname{dis}(i,j)\) 表示新序列上 \(i,j\) 点之间的距离。特别地，方便起见，令原序列上的 \(k\) 在新序列的第 \(n\) 位上，故 DP 过程仅为前 \(n-1\) 位的决策，与第 \(n\) 位无关。
转移式子： \[ f(l,r,0) = \min{\large\{}f(l + 1,r,0) + \operatorname{dis}(l, l + 1), f(l + 1,r,1) + \operatorname{dis}(r, l)\large\} \] \[ f(l,r,1) = \min{\large\{}f(l,r - 1,0) + \operatorname{dis}(l, r),f(l,r - 1,1) + \operatorname{dis}(r - 1, r)\large\} \] 输出方案可以在记录一个 \(p(l,r,0/1)=0/1\) 表示在区间 \(l\sim r\) 的左 \(/\) 右时，上一次是从左 \(/\) 右转移来，递归输出方案。
1 | inline double Dis(int i, int j) { |
H - 括号序列再战猪猪侠 by Lydic
根据题目要求，容易想到区间计数动态规划。
我们只考虑左括号，设 \(dp_{l,r}\) 表示当前考虑从第 \(l\) 到第 \(r\) 个左括号时的方案数，注意，这里的状态同时包含了这些左括号对应的右括号。
考虑转移，我们设 A 为一个合法括号串，它表示的区间是
\([l,r]\)，可以很自然的分三种情况：
(A)，此时需满足 \([l,r]\) 中所有右括号都没有要求大于第 \(l-1\) 个左括号的右括号的限制。()A，此时和上面类似，需满足 \([l,r]\) 中所有右括号都没有要求小于第 \(l-1\) 个左括号的右括号的限制。(A，同时把A从中间断开插入右括号，设当前枚举的断点为 \(k\)，此时需满足 \([l,k]\) 中所有右括号都没有要求大于第 \(l-1\) 个左括号的右括号的限制，以及 \([l-1,k]\) 中所有右括号都没有要求大于区间 \([k+1,r]\) 中所有左括号的右括号的限制。
对于这些限制的快速判断我们可以维护一个矩阵，每条信息相当于矩阵上的一个点，这样对于前文的要求可以快速用二位前缀和的值的存在与否判断是否全部满足。
1 | int ask(int l1, int r1, int l2, int r2) { |
I - [THUSC2016] 成绩单 by zhujiangyuan
当你列出 DP 状态发现无法转移的时候，不妨添加状态。
设 \(f_{i,j,l,r}\) 为要消除 \([i,j]\) 区间，且当前未消除的数值域均在 \([l,r]\) 时的最小代价。
设 \(dp_{i,j}\) 为消除 \([i,j]\) 区间的最小代价。
则 \(dp_{i,j}=\min f_{i,j,l,r}+a+b\times (r-l)^2\)。
转移：
枚举断点，合并两个区间。\(f_{i,j,l,r}=\min\limits_{k=i}^{j-1} f_{i,k,l,r}+f_{k+1,j,l,r}\)。
找到 \([i,j]\) 区间中最靠左的值域不在 \([l,r]\) 的数位置，记为 \(p\)，找到最靠右的值域不在 \([l,r]\) 的数的位置，记为 \(q\)。则 \(f_{i,j,l,r}=dp_{p,q}\)。
枚举 \(i,j,l,r\) 时间复杂度 \(\mathcal O(n^4)\)，枚举断点 \(\mathcal O(n)\)，总时间复杂度 \(\mathcal O(n^5)\)。
1 | for (int i = 1; i <= n; i++) { |
J - [CQOI2007] 涂色 by Lydic
考虑一个结论：一定存在一种最优方案使得使得任意一次染色的区间一定是完全包含之前某一次染色区间或者与之前某一次染色区间完全不交且不与之前所有染色区间相交。
简单证明，如果我们当前的染色方案与之前某一次相交，那么我们完全可以缩短当前染色区间使得不交。
我们发现这个性质能够把染色的过程抽象为类似线段树的结构，即线段与线段之间只存在包含和并列的关系，一个大区间的答案可以由其中的小区间合并而来，于是我们可以想到用区间 DP 解决这个问题。
这样我们设 \(dp_{l,r}\) 表示染色区间为 \(l,r\) 时的答案，对上述两种情况分别考虑：
完全包含。此时一定有 \(s_l=s_r\)，那么 \(dp_{l,r}\) 可以由 \(dp_{l,r-1}\) 和 \(dp_{l+1,r}\) 转移过来。具体的，比如对于
ABA，它可以由AB直接转移，即第一次染色时可以向右端点多染一次。这里可能会有疑问，也许这种染色方式会不满足上文条件。但其实不要紧，因为就算不满足我们也可以通过前文的转化方式使其满足条件。等价于转移时不需要完全满足上文条件。完全不相交。我们在这里其实只需要考虑紧挨的情况，即类似
AABB，因为不紧挨的情况可以由多个紧挨的情况转移过来。所以只需要枚举断点 \(k\)，合并累加两段答案即可。
1 | scanf("%s", s + 1), n = strlen(s + 1), memset(dp, 0x3f, sizeof dp); |
K - [ZJOI2016] 线段树 by Lydic
首先，题目上说让期望乘上 \((\frac{n(n+1)}{2})^q\) 的目的就是让我们求方案数与值的乘积。
然后我们考虑在操作过后一个位置上的值相对于原来的值肯定是不降的，于是可以想到对每一个值 \(v\) ，原序列中所有 \(\le v\) 的元素一定构成了若干连续的区间。对每一个这样的区间而言，操作过后这个区间的左右端点一定是向中间移动的。
于是我们可以对每个区间都考虑一个 DP。设 \(dp_{v,x,l,r}\) 表示操作 \(x\) 次后区间 \([l,r]\) 中的数字均 \(\le v\)，且第 \(l-1\) 和 \(r+1\) 个元素都 \(\gt v\) 的方案数。
转移的话显然可以从 \(dp_{v,x-1,l,r},dp_{v,x-1,i,r},dp_{v,x-1,l,i}\) 转移过来。具体的，第一种转移相当于第 \(x\) 次操作对于区间 \([l,r]\) 来说应该是无用的，即操作区间 \([1,l-1],[l,r],[r+1,n]\) 的总方案数。第二种和第三种转移类似，以第二种为例，相当于第 \(x\) 次操作应当在区间 \([1\sim i-1,l-1]\) 进行，这个可以使用两个前缀和优化。转移方程就不写了，其中 \(x\) 这一维显然可以滚掉。
回到题面，我们现在要解决的问题就是求每个数字最终大小为某个定值时的方案数。上述 DP 求的是每个区间最终值不大于某个定值时的方案数，那我们对于一个区间 \([l,r]\) 而言，若用 \(f(j)\) 表示 \(dp_{j,q,l,r}\)，那么这个区间最终值等于 \(j\) 的方案数显然就是 \(f(j)-f(j-1)\)。
这样对于每一个元素，我们只需要找到所有包含它的区间，再对于这个元素在该区间内可能变成的所有值都累加答案即可。根据定义，可以保证方案不会重复。
根据数据随机的条件，时间复杂度近似 \(\mathcal{O}(n^2q)\)，可以通过本题。
但是还有更优的做法。我们发现，对于每一个值 \(v\)，它所带来的系数是固定的，所以我们可以对 \(v\) 这一维直接乘上对应的系数后求和，把总维度优化到三个，用数组 \(dp'_{x,l,r}\) 直接表示操作 \(x\) 次后区间 \([l,r]\) 的答案，这样我们可以发现转移与上文所述完全一致，不同点在于初值。
具体的，在赋初值的时候我们枚举区间 \([l,r]\)，设 \(ma\) 为初始序列中下标为 \(l-1\) 和 \(r+1\) 元素的最小值，同时设 \(num\) 表示区间 \([l,r]\) 中元素的最大值，那么可以推出 \(dp'_{0,l,r}=num-ma\)。
1 | inline int calc(int l, int r) { |
L - CF1987F Interesting Problem by Heldivis
考察一个数 \(a_i\) 能被删去的条件：
- 由于每次删除的性质，下标只会越来越小，并且奇偶性不变。所以必须满足 \((a_i\le i)\land(a_i\equiv i\pmod2)\)。
- 可以在 \([1,r)\) 的范围内恰好进行 \(\dfrac{i-a_i}{2}\) 次操作使得 \(a_i\) 和 \(i\) 相等。
条件 1. 是好维护的，考虑针对条件 2. 进行 DP：设 \(f(l,r)\) 表示删空 \(l\sim r\) 所需要的最少操作前缀 \([1,l)\) 次数，转移如下：
\(a_l\) 和 \(a_r\) 同时消去 那么需要进行完删空 \(l+1\sim r-1\) 的操作后，仍满足条件 1. 使得可以对 \(a_l\) 操作，即 \(f(l+1,r-1)\le\dfrac{l-a_l}{2}\)（或区间仅有两个数）： \[ f(l,r) \xleftarrow[\large f(l+1,r-1)\le\frac{l-a_l}{2}\lor r-l=1]{\min} \dfrac{l - a_l}{2} \]
枚举断点 \(k\) 那么需要进行若干次操作，使得 \(a_l=l\)，同时至少要满足左半部分清空的 \(f(l,k-1)\) 的代价，以及右半部分 \(f(k+1,r)-\dfrac{k-l+1}{2}\) 的代价，减去是清空左半部分时的贡献。也就是： \[ f(l,r) \xleftarrow{\min} \max\left\{\dfrac{l - a_l}{2},f(l,k)+f(k+1,r)-\dfrac{k-l+1}{2}\right\} \]
然后发现你会 \(\texttt{Wrong answer on test 20}\)
因为你状态设的是设 \(f(l,r)\) 表示删空 \(l\sim r\) 所需要的最少操作前缀 \([1,l)\) 次数，所以当左半部分清空之后，右半部分 \(f(k+1,r)-\dfrac{k-l+1}{2}\) 的代价是独立计算的。所以第一个转移为： \[ f(l,r) \xleftarrow{\min} \max\left\{\dfrac{l - a_l}{2},f(l,k),f(k+1,r)-\dfrac{k-l+1}{2}\right\} \]
然后你就得到了 \(f(l,r)\)，然后你发现答案不是 \(f(1,n)\)。废话
考虑 \(f(l,r)\) 的含义是删空区间 \(l\sim r\) 的一个限制，删空区间 \(l \sim r\) 的价值是 \(\dfrac{r-l+1}{2}\)，所以考虑通过这个限制 & 贡献再跑一次 DP。
设 \(dp_i\) 表示前 \(i\) 个数的最优解，那么有转移： \[ dp_i=\max_{2|(i-j+1)}\left\{dp_{j-1} + \dfrac{i-j+1}{2}\right\}\quad \] 最后答案就是 \(dp_n\) 了。
代码就是模拟以上 DP，注意区间长度恒为偶数，记得赋初值。
1 | n = read(); for (int i = 1; i <= n; ++i) a[i] = read(); |
M - [THUPC2021] 小 E 爱消除 by Heldivis
简要题意
从一个序列两端取数放入栈中，栈中有两个数相同即可消去。求最后栈内元素最少值，和在此条件下栈最大空间最小值。
转移 1
设 \(f(l,r)=(x,y)\) 表示区间 \(l\sim r\) 中，最少剩 \(x\) 个，此时最小空间为 \(y\)。
考虑转移：
- 不操作，直接将 \(a_l/a_r\) 放入栈中：
\[ f(l,r)\xleftarrow{\min}\min\{f(l + 1, r), f(l, r - 1)\}+ (1, 1) \]
使 \(a_l\) 和某一个数匹配：
考虑枚举和它匹配的 \(i\) 使得 \(a_i = a_l\)，那么就需要两个数同时再序列两端（\(a_l,\dots,a_i\)），或同时在序列同一端（\(a_l,a_i,\dots\)）。
变换至序列两端：
那么就需要取出 \([i+1,r]\) 的数字，同时有可能去除 \([l+1,j]\)（\(j\lt i\)）的一段数字去和 \([i+1,r]\) 匹配消去。
设 \(g(l_1,r_1,l_2,r_2)\) 表示删去 \([l_1,r_1]\cap[l_2,r_2]\) 所需要的最大空间，则有转移： \[ f(l,r)\xleftarrow{\min}\min{\LARGE\{}{\Large(}f(j+1,i-1)\mathrm{.first},\max{\large\{}2,f(j+1,i-1)\mathrm{.second},g(l+1,j,i+1,r)+1{\large\}}{\Large)}{\LARGE\}} \]
变换至序列一端：
同理需要取出 \([l+1,i-1]\) 的数字，同时可能去除 \([j,r]\)（\(j\gt i\)）的一段数字和 \([l+1,i-1]\) 匹配消去。
转移： \[ f(l,r)\xleftarrow{\min}\min{\LARGE\{}{\Large(}f(i + 1,j - 1)\mathrm{.first},\max{\large\{}2,f(i+1,j-1)\mathrm{.second},g(l+1,i-1,j,r)+1{\large\}}{\Large)}{\LARGE\}} \]
以上两种在代码中实现是可以令
j\(= j+1\) 就不用分讨了。
使 \(a_r\) 和某一个数匹配：
同理分为变换至序列两端、变换至序列一端两类，转移类似。
转移 2
然后中间有个 \(g(l_1,r_1,l_2,r_2)\)，考虑它的转移：
使 \(a_{l_1}\) 和某一个匹配：
枚举 \(i \in[l_1,r_1]\) 且 \(a_i = a_{l_1}\)：
找一个 \(j\in[l_2-1,r_2]\)（\(j=l_2-1\) 相当于不选另一个区间），有转移： \[ g(l_1,r_1,l_2,r_2)\xleftarrow{\min}\max(g(i + 1, r_1, l_2, j), g(l1 + 1, i - 1, j + 1, r_2) + 1) \] 即：消去内部的空间，消去外部的和这次空间，两者最大值。
枚举 \(i \in[l_2,r_2]\) 且 \(a_i = a_{l_1}\)
使 \(a_{r_2}\) 和某一个匹配
- 枚举 \(i \in[l_1,r_1]\) 且 \(a_i = a_{r_2}\)
- 枚举 \(i \in[l_2,r_2]\) 且 \(a_i = a_{r_2}\)
其实 \(f,g\) 的转移都是相似的，所以就做完了。
时间复杂度
\(g\) 的状态是 \(O(n^2)\) 的，转移是 \(O(n^2)\) 的，一共 \(O(n^4)\) 能过。
\(f\) 的状态是 \(O(n^4)\) 的，转移是 \(O(n^2)\) 的，一共 \(O(n^6)\)。\(50^6\approx1.5\times10^{10}\)，但是枚举 \(i,j\) 的时候有范围限制，跑出来转移次数在 \(10^9\) 左右，肯定还跑不满，卡卡常就过了。
代码
细节比较多：
- DP 过程可以记忆化，
记忆化没记忆化上结果瞎卡了十分钟常 TvT。 l1r1r2l2会很乱。写错一个调了二十分钟 TvT。
1 | using pii = pair<int, int>; |