题解

问题分析

题目要求通过添加/删除边，使得 $[1,2,\dots,N]$ 成为一个可能的 DFS 序，并且总代价最小。

关键观察

1. DFS 序的性质：在 DFS 树中，节点 $1$ 是根，每个节点的 DFS 序必须大于其父节点
2. 区间结构：DFS 树可以递归地分解为子树区间
3. 代价计算：需要计算在构建特定 DFS 树结构时的最小代价

算法思路

区间动态规划：

状态定义

• dp[i][j]：将区间 $[i,j]$ 构建成以 $i$ 为根的子树，且 DFS 序恰好为 $[i,i+1,\dots,j]$ 的最小代价

状态转移

对于区间 $[i,j]$，枚举根 $i$ 的第一个子节点 $k$：

• 左子树：区间 $[i+1, k-1]$（如果存在）
• 右子树：区间 $[k, j]$
• 转移方程：

  dp[i][j] = min(dp[i][k-1] + dp[k][j] + cut(i+1,j,k) + cost(i,k))
  

  其中：
  • cut(i+1,j,k) 是删除某些边的代价
  • cost(i,k) 是添加边 $(i,k)$ 的代价（如果需要）

预处理

• 二维前缀和 s 用于快速计算子矩阵和
• cut 函数计算需要删除的边

核心代码逻辑

代价计算函数

auto cut = [&](int i, int j, int k) {
    auto sum = [&](int i, int j) {
        if(i >= j) return 0;
        return s[j][j] - s[i-1][j] - s[j][i-1] + s[i-1][i-1];
    };
    return sum(i,j) - sum(i,k-1) - sum(k,j);
};

动态规划转移

for(int j=1; j<=n; ++j)
    for(int i=j-1; i>=1; --i)
        for(int k=i+1; k<=j; ++k)
            dp[i][j] = min(dp[i][j], 
                dp[i][k-1] + dp[k][j] + 
                cut(i+1, j, k) + 
                (a[i][k] > 0) * a[i][k]);

算法步骤

1. 输入处理：读入代价矩阵 a
2. 预处理：计算删除边的代价前缀和 s
3. 初始化：dp[i][i] = 0
4. 区间DP：按区间长度从小到大计算
5. 输出：dp[1][n] 即为答案

复杂度分析

• 预处理：$O(N^2)$
• 动态规划：$O(N^3)$，在 $N \leq 750$ 时可行
• 总复杂度：$O(N^3)$

样例验证

样例1：$N=4$

• 初始无边，需要构建边 $(1,2),(2,3),(2,4)$
• 代价：$1 + 3 + 6 = 10$
• 输出正确

样例2：$N=5$

• 初始有边 $(1,2),(2,3),(2,4),(1,5),(2,5),(3,5)$
• 只需移除边 $(3,5)$，代价 $5$
• 输出正确

算法标签

• 区间动态规划
• DFS树构造
• 图论
• 最优化
• 前缀和优化