CF区间DP作业题解

1. Recovering BST

由于互质关系不是传递的，所以尽量挂在树的最下面，刚好构成二叉树

f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0] 表示区间 [ i , j ] [i,j] [i,j] 以 i i i 为根，是否可以构成一棵树。

f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1] 表示区间 [ i , j ] [i,j] [i,j] 以 j j j 为根，是否可以构成一棵树。

1. 先按照任意两点的最大公约数是否大于 1 建边；
2. 当 f [ i ] [ k ] [ 0 ]   & &   f [ k + 1 ] [ j ] [ 1 ] f[i][k][0]\ \&\&\ f[k+1][j][1] f[i][k][0] && f[k+1][j][1] 为真时，可以考虑将左边的树挂到 k + 1 k+1 k+1 下方，或者将右边的树挂到 k k k 下方，连成一棵树，即可转换为一棵二叉树。
3. 答案即为所有 f [ 1 ] [ i ] [ 1 ]   & &   f [ i ] [ n ] [ 0 ] ( 1 ≤ i ≤ n ) f[1][i][1]\ \&\&\ f[i][n][0](1\le i\le n) f[1][i][1] && f[i][n][0](1≤i≤n) 中是否存在一个 i i i 可以使得式子为真。

2. Minimum Triangulation

首先，可以直接使用区间DP完成 O ( n 3 ) O(n^3) O(n3)。

但这题有一个更简单的实现：使得每个三角形都有顶点 1，可以得到最优答案：
∑ i = 2 n − 1 i ⋅ ( i + 1 ) \sum_{i=2}^{n-1}i\cdot(i+1) i=2∑n−1​i⋅(i+1)

证明：

我们考虑边 ( 1 , n ) (1,n) (1,n) 可以构成一个三角形 [ 1 , n , x ] [1,n,x] [1,n,x](三角形的三个顶点)。

• 如果 x = n − 1 x=n-1 x=n−1，我们就可以删除一个三角形，得到剩余的规模为 n − 1 n-1 n−1 的子问题；
• 否则， 1 < x < n − 1 1\lt x\lt n-1 1<x<n−1，将原来的图形分成了左右两个部分，其中 x ∼ n x\sim n x∼n 的点构成一个多边形（不是三角形），我们再选取 k ( x < k < n ) k(x\lt k\lt n) k(x<k<n) 点构成一个三角形 [ n , x , k ] [n,x,k] [n,x,k]，这时， [ 1 , x , k , n ] [1,x,k,n] [1,x,k,n] 构成一个四边形，对于这个四边形，显然划分成 [ 1 , n , k ] [1,n,k] [1,n,k] 和 [ 1 , n , x ] [1,n,x] [1,n,x] 比划分成 [ 1 , n , x ] [1,n,x] [1,n,x] 和 [ n , x , k ] [n,x,k] [n,x,k] 更优，因为 1 ⋅ n ⋅ k + 1 ⋅ k ⋅ x < x ⋅ n ⋅ k + 1 ⋅ n ⋅ x 1\cdot n\cdot k+1\cdot k\cdot x\lt x\cdot n\cdot k+1\cdot n\cdot x 1⋅n⋅k+1⋅k⋅x<x⋅n⋅k+1⋅n⋅x。

注意：将三角形 [ 1 , n , x ] [1,n,x] [1,n,x] 转换为 [ 1 , n , k ] ( k > x ) [1,n,k](k\gt x) [1,n,k](k>x)，可以持续递推，直至 x = n − 1 x=n-1 x=n−1。

综上，我们可以将任意三角划分按照这个原则进行改进，且绝不会增加权值。

3. Connecting Vertices

考虑任意一个区间 [ i , j ] [i,j] [i,j] 尚未连通，其子区间已经构成两个连通分量，可以选择：

（1）将 i i i 和 j j j 连接；

（2）不连 i i i 和 j j j，将中间某个结点连接。

上面两种方案没有交集，方案数直接相加即为 [ i , j ] [i,j] [i,j] 做成连通图的答案，不需要容斥。

令 f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0] 表示区间 [ i , j ] [i,j] [i,j] 连通且 i i i 和 j j j 不邻接的方案数； f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1] 表示区间 [ i , j ] [i,j] [i,j] 连通且 i i i 和 j j j 邻接的方案数。

4. Clear the String

令 f [ i ] [ j ] f[i][j] f[i][j] 为将区间 [ i , j ] [i,j] [i,j] 删除需要的最小魔法值消耗。

按两种情况考虑：

（1） s [ i ] = = s [ i + 1 ] s[i] == s[i+1] s[i]==s[i+1]

（2）枚举中间分割点 k k k