加训区间 DP

区间 DP 越来越多，我该怎么办？区间 DP 越来越多，我该怎么办？区间 DP 越来越多，我该怎么办？区间 DP 越来越多，我该怎么办？区间 DP 越来越多，我该怎么办？区间 DP 越来越多，我该怎么办？区间 DP 越来越多，我该怎么办？区间 DP 越来越多，我该怎么办？

1. CSP-S 2021 T2 括号序列

大力分讨题。

一种思路是枚举左括号对应的右括号，但是这样太慢了。

考虑区间 $\text{DP}$ 时，$len$ 更小的区间总会被先枚举到。

因此我们只要令 $f_{i,j} \gets f_{i+1, j-1}$ 就可以处理好加括号的操作了。

注意讨论清楚不同形式的括号序列，具体可以看 Enucai 的 题解。

2. 云斗 10 月 Golden Round T2 论整齐度与美观

题意：给你一个长度为 $n$ 的排列 $p$，每次可以删排列头部或尾部的一个元素，记 $q_i$ 为第 $i$ 次取到的数，求 $\min\{\sum_{i<j<k}{[q_i<q_j<q_k]}\}$。

由于传统方式不太好处理，考虑将答案贡献算到 $j$ 头上。时间倒流，则往 $[l,r]$ 中加一个数 $x$ 对答案的贡献为 $\sum_{i\in[l,r]}{[p_i>x]}\cdot\sum_{i\not\in[l,r]}{[p_i<x]}$，即区间内大于 $x$ 的数的个数与区间外小于 $x$ 的数的个数之积。

暴力 $\text{DP}$ ，枚举选区间左端点还是右端点，并预处理前缀小于某个数的个数，时间 $O(n^2)$，空间 $O(n^2)$，可以拿到 $45$ 分左右。

考虑优化空间。注意到一种区间 $\text{DP}$ 方式为记录区间长度 $len$ 和左端点 $i$，可以使用滚动数组优化，将 $\text{DP}$ 数组的空间复杂度降到 $O(n)$。

考虑如何优化预处理的空间。

注意到每次「询问」的区间长度是与当前转移长度相同的。考虑记 $g_i$ 为当前正在计算长度为 $len$ 区间的答案，$[i, i+len-1]$ 区间中小于等于 $p_i$ 的数的个数，记 $h_i$ 为 $[i - len + 1, i]$ 区间中小于等于 $p_i$ 的数的个数。

则转移时需要的量可以 $O(1)$ 由 $g,h$ 求出。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$，可以 AC。

3. BJWC 2018 序列合并

题意：长度为 $n$ 的序列，每次可以合并一个长度在 $[L,R]$ 中的连续区间，代价为区间内数的和，合并完后将这些数替换为（$1$ 个）他们的和。求将整个序列合并为一个数的最小代价。

注意到如果要合并掉一个区间内的值，一定会先在这个区间内做若干次合并，直到区间长度在 $[L,R]$ 中为止。

记 $f_{i,j}$ 为将 $[i,j]$ 合并成一个区间所需的最小代价。

定义辅助数组 $g_{i,j,k}$ 为将 $[i,j]$ 合并成 $k$ 段区间的最小代价。

转移时枚举最后一段区间的左端点 $p$，则 $g_{i,j,k}\gets g_{i,p-1,k-1}+f_{p,j}$。

暴力做是 $O(n^5)$ 的，需要优化。

注意到 $g$ 的转移有点重复：具体来说，对于相同的左端点 $i$，不同的右端点 $j$，其有一段共用的转移部分。

到这里开始引入一种人类智慧的区间 $\text{DP}$ 方法：我们不枚举区间长度，而是枚举左端点，右端点，其中左端点降序枚举，右端点升序枚举，容易证明这样枚举是不重不漏的。

具体来说，我们在枚举右端点时，动态地将新算出的 $f_{i,j}$ 加入 $g$ 的转移。

For(i, 1, n) f[i][i] = 0;
ForDown(i, n, 1) {
  memset(g, 0x3f, sizeof(g));
  For(j, i + 1, n) {
    g[1][j - 1] = f[i][j - 1];
    For(k, 2, min(j - i + 1, R)) { // [i, j] 分成 k 段
        For(p, i, j) { g[k][j] = min(g[k][j], g[k - 1][p - 1] + f[p][j]); }
    }
    For(k, L, R) {
      f[i][j] = min(f[i][j], g[k][j] + sum[j] - sum[i - 1]);
    }
  }
}

时间复杂度 $O(n^4)$，由于内存访问极其连续而且跑不满，常数非常小，可以通过本题。

4. KDOI-06-S T3 合并序列

重头戏。

DP 开心小水鸟，卡常难过大火鱼。

考虑多项式复杂度的做法：记 $f_{i,j}$ 表示 $[i,j]$ 这个区间能否被消成一个数。

发现如果可以，一定采用如下的做法：

[xxxxx____yyyy__zz]

其中 x 段贴着左端点，z 段贴着右端点，x,y,z 三段都能被消成一个数，并且三段中的数异或和为 $0$。

暴力转移即为 $O(n^6)$。

考虑优化 $1$：我们枚举 x 段右端点和 z 段左端点。那么 y 段中的数异或和是已知的，我们可以计算出 $g_{i,j,k}$ 表示 $[i,j]$ 区间中是否存在一段异或和为 $k$ 的区间，满足可以被消成一个数。

时间复杂度 $O(n^4)$，听说卡卡常还能过？

考虑优化 $2$：$f$ 只记一个 bool 非常浪费状态。

定义一个区间「合法」，当且仅当它能被消成一个数。

具体而言，我们发现如果 $f_{i_0,j_0}=1$ 且这组解对应的 z 段异或和为 $k$，那么对于所有的 $[i,j]$，满足 $i=i_0,j\ge j_0$ 并且 z 段异或和为 $k$，它都合法。

我们记 $g_{i,j}$ 为所有 左端点 下标大于等于 $i$，并且区间异或和为 $j$ 的 合法 区间中，最小 的右端点；

记 $h_{i,j}$ 为 x 段 左端点恰好为 $i$，x, y 两段均合法，且这两段中数异或和为 $j$ 的所有方案中，最小的 $y$ 段右端点。

容易发现，$g$ 的作用是转移 y 段，$h$ 的作用是转移 x 段。

在转移时，我们枚举 z 段长度 $len$，记 z 段异或和为 $k$，则 $f_{i,j} \gets (f_{j-len+1,j}\land [h_{i,k} \le j-len])$。

使用上文的「人类智慧 $\text{DP}$ 顺序」即可。

注意到这道题也不能使用正常的区间 $\text{DP}$，因为大区间的 $g$ 可能参与了小区间的 $h$ 的转移。

什么还要输出方案？$\text{DP}$ 过程中记录一下 $f,g,h$ 的决策点，然后 $\text{DFS}$ 输出即可。

你可能需要卡常，包括但不限于在 $f_{i,j}$ 等于 $1$ 时退出一些循环。