1. Recovering BST
由于互质关系不是传递的,所以尽量挂在树的最下面,刚好构成二叉树
f[i][j][0]f[i][j][0]f[i][j][0] 表示区间 [i,j][i,j][i,j] 以 iii 为根,是否可以构成一棵树。
f[i][j][1]f[i][j][1]f[i][j][1] 表示区间 [i,j][i,j][i,j] 以 jjj 为根,是否可以构成一棵树。
- 先按照任意两点的最大公约数是否大于 1 建边;
- 当 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+1k+1k+1 下方,或者将右边的树挂到 kkk 下方,连成一棵树,即可转换为一棵二叉树。
- 答案即为所有 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) 中是否存在一个 iii 可以使得式子为真。
2. Minimum Triangulation
首先,可以直接使用区间DP完成 O(n3)O(n^3)O(n3)。
但这题有一个更简单的实现:使得每个三角形都有顶点 1,可以得到最优答案:
∑i=2n−1i⋅(i+1)\sum_{i=2}^{n-1}i\cdot(i+1) i=2∑n−1i⋅(i+1)
证明:
我们考虑边 (1,n)(1,n)(1,n) 可以构成一个三角形 [1,n,x][1,n,x][1,n,x](三角形的三个顶点)。
- 如果 x=n−1x=n-1x=n−1,我们就可以删除一个三角形,得到剩余的规模为 n−1n-1n−1 的子问题;
- 否则,1<x<n−11\lt x\lt n-11<x<n−1,将原来的图形分成了左右两个部分,其中 x∼nx\sim nx∼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⋅x1\cdot n\cdot k+1\cdot k\cdot x\lt x\cdot n\cdot k+1\cdot n\cdot x1⋅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−1x=n-1x=n−1。
综上,我们可以将任意三角划分按照这个原则进行改进,且绝不会增加权值。
3. Connecting Vertices
考虑任意一个区间 [i,j][i,j][i,j] 尚未连通,其子区间已经构成两个连通分量,可以选择:
(1)将 iii 和 jjj 连接;
(2)不连 iii 和 jjj,将中间某个结点连接。
上面两种方案没有交集,方案数直接相加即为 [i,j][i,j][i,j] 做成连通图的答案,不需要容斥。
令 f[i][j][0]f[i][j][0]f[i][j][0] 表示区间 [i,j][i,j][i,j] 连通且 iii 和 jjj 不邻接的方案数;f[i][j][1]f[i][j][1]f[i][j][1] 表示区间 [i,j][i,j][i,j] 连通且 iii 和 jjj 邻接的方案数。
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)枚举中间分割点 kkk