F. 旅行售卖猫 详细题解

问题重述

有 $n$ 个城市，第 $i$ 个城市有两个参数 $a_i, b_i$。
两个不同城市 $i, j$ 之间的道路长度为 $\max(a_i + b_j,\; a_j + b_i)$。
一条简单路径的代价为路径上相邻城市道路长度之和。
对于每个 $k = 2, 3, \dots, n$，求恰好经过 $k$ 个不同城市的所有简单路径中的最小代价。

核心观察与排序

定义 $d_i = b_i - a_i$。
将城市按照 $d_i$ 升序排序，即 $d_1 \le d_2 \le \dots \le d_n$。
排序后，对于 $i < j$，有 $a_i + b_j \ge a_j + b_i$，因此

$$\max(a_i + b_j,\; a_j + b_i) = a_i + b_j.$$

这个性质使得在排序序列中从左到右的边权容易计算。

问题转化为线性 DP

考虑一条简单路径，将其顶点按在排序后的位置重新排列。可以证明（通过交换论证）存在一条最优路径，其顶点在排序后的序列中构成一个连续区间。
因此，我们只需考虑所有区间 $[l, r]$（$1 \le l \le r \le n$），长度为 $len = r-l+1$，并计算以某种顺序经过这些点的最小代价。

对于区间 $[l, r]$，有两种可能的顺序：从左到右或从右到左。

• 从左到右：代价为 $a_l + (a_{l+1}+b_l) + (a_{l+2}+b_{l+1}) + \dots + (a_r+b_{r-1})$，简化后为 $\sum_{i=l}^{r} (a_i+b_i) - b_l$？需要仔细推导。

实际上，设排序后点的坐标为 $p_1, p_2, \dots, p_n$，并记其 $a, b$ 值。对于路径 $p_l \to p_{l+1} \to \dots \to p_r$：

• 边 $p_i \to p_{i+1}$ 长度 = $a_{p_i} + b_{p_{i+1}}$（因为 $i < i+1$）。
• 总代价 = $\sum_{i=l}^{r-1} (a_{p_i} + b_{p_{i+1}}) = \left(\sum_{i=l}^{r-1} a_{p_i}\right) + \left(\sum_{i=l+1}^{r} b_{p_i}\right)$。
• 记 $S = \sum_{i=l}^{r} (a_{p_i}+b_{p_i})$，则上式 = $S - a_{p_r} - b_{p_l}$。
  类似地，逆序路径 $p_r \to p_{r-1} \to \dots \to p_l$ 的代价为 $S - a_{p_l} - b_{p_r}$。
  因此区间 $[l,r]$ 的最优路径代价为

$$\mathrm{cost}(l,r) = \sum_{i=l}^{r} (a_i+b_i) - \max(a_l+b_r,\; a_r+b_l). $$

于是问题变成：对每个长度 $k$，求所有区间 $[l,r]$ 满足 $r-l+1 = k$ 的最小 $\mathrm{cost}(l,r)$。

动态规划优化（标程采用的方法）

直接枚举区间 $O(n^2)$ 对于 $n\le 3000$ 且 $\sum n^2 \le 9\times10^6$ 已经可行，但标程使用了一种更巧妙的 DP，将每个点依次加入，维护路径的当前状态，从而在 $O(n^2)$ 内同时计算所有 $k$ 的答案。

状态定义

设 $dp[j][t]$ 表示当前已经考虑了排序后的前若干个点，并已选出了 $j$ 个点构成一条未完成的路径，其中 $t$ 表示路径的形态：

• $t=0$：路径只有一个点（即只确定了起点，没有边）。
• $t=1$：路径有两个端点，但只记录了 左端点的贡献（实际上状态设计很精巧，需结合转移理解）。
• $t=2$：路径已经完整（两个端点都已计入），可以用于更新答案。

初始时 $dp[0][0]=0$，其余为 $\infty$。

转移

按排序顺序依次加入新点 $x$（即城市 $p_i$）。
设当前点为 $x$，其参数为 $a, b$。
我们考虑将 $x$ 加入已有的路径：

1. 作为新路径的第一个点：
   如果路径长度为 $1$，则起点贡献为 $2a$（因为首尾都要算？标程中 $tdp[1][0] = \min(2a)$，$tdp[1][1] = \min(a)$）。
2. 作为路径的中间点：
   从任意状态 $dp[j][t]$ 扩展，新路径长度 $j+1$，状态 $t$ 不变，代价增加 $a+b$（因为 $x$ 作为内部点，会贡献 $a$ 和 $b$ 各一次）。
3. 作为路径的右端点（即终结当前路径）：
   • 若当前状态为 $t=0$（只有一个点），则添加 $x$ 后形成两个点，状态变为 $t=1$，代价增加 $b$（右端点的 $b$ 贡献）。
   • 若当前状态为 $t=1$（已有一个端点），则添加 $x$ 后形成完整路径，状态变为 $t=2$，代价增加 $a$（右端点的 $a$ 贡献）。
   • 同时，当形成完整路径（$t=2$）时，还可以更新答案：$ans[j+1] = \min(ans[j+1], dp[j][2] + 2b)$（对应路径右端点贡献两次 $b$）。

具体转移方程（用辅助数组 $tdp$ 暂存）：

• $tdp[1][0] = \min(tdp[1][0],\; 2a)$
• $tdp[1][1] = \min(tdp[1][1],\; a)$
• 对于 $j=1..n-1$：
  • $tdp[j+1][t] = \min(tdp[j+1][t],\; dp[j][t] + a + b)$（插入中间）
  • $tdp[j+1][1] = \min(tdp[j+1][1],\; dp[j][0] + b)$（从单点扩展）
  • $tdp[j+1][2] = \min(tdp[j+1][2],\; dp[j][1] + a)$（从两个端点之一扩展成完整路径）
  • 更新答案：
    • $ans[j+1] = \min(ans[j+1],\; dp[j][1] + b)$
    • $ans[j+1] = \min(ans[j+1],\; dp[j][2] + 2b)$

最后将 $tdp$ 合并到 $dp$，继续下一个点。

算法步骤

1. 读入 $t$。
2. 对于每个测试用例：
   • 读入 $n$ 及所有 $(a_i,b_i)$。
   • 按 $b_i - a_i$ 升序排序。
   • 初始化 $dp$、$tdp$ 为无穷大，$ans$ 为无穷大。
   • 对每个点 $i$ 执行上述转移。
   • 输出 $ans[2], ans[3], \dots, ans[n]$。

复杂度

• 排序 $O(n\log n)$。
• DP 共 $n$ 个点，每个点内循环 $O(n)$，总 $O(n^2)$。
• 空间 $O(n)$。
• 满足 $\sum n^2 \le 9\times10^6$。

代码实现（标程原样，添加注释）

#include<bits/stdc++.h>
using namespace std;

struct apos {
    long long a, b;
    // 按 b-a 升序排序
    friend bool operator<(apos x, apos y) {
        return x.b - x.a < y.b - y.a;
    }
} ap[3000];

long long dp[3001][3], tdp[3001][3], ans[3001];
const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        for (int i = 0; i < n; ++i) cin >> ap[i].a >> ap[i].b;
        sort(ap, ap + n);

        // 初始化
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j < 3; ++j) dp[i][j] = tdp[i][j] = INF;
            ans[i] = INF;
        }

        for (int i = 0; i < n; ++i) {
            long long a = ap[i].a, b = ap[i].b;

            // 当前点作为第一个点
            tdp[1][0] = min(tdp[1][0], 2 * a);
            tdp[1][1] = min(tdp[1][1], a);

            for (int j = 1; j < n; ++j) {
                // 插入中间
                for (int t = 0; t < 3; ++t)
                    tdp[j+1][t] = min(tdp[j+1][t], dp[j][t] + a + b);
                // 作为右端点扩展
                tdp[j+1][1] = min(tdp[j+1][1], dp[j][0] + b);
                tdp[j+1][2] = min(tdp[j+1][2], dp[j][1] + a);
                // 更新答案（形成完整路径）
                ans[j+1] = min(ans[j+1], dp[j][1] + b);
                ans[j+1] = min(ans[j+1], dp[j][2] + 2 * b);
            }

            // 将 tdp 合并到 dp
            for (int j = 1; j <= n; ++j) {
                for (int t = 0; t < 3; ++t) {
                    dp[j][t] = min(dp[j][t], tdp[j][t]);
                    tdp[j][t] = INF;
                }
            }
        }

        // 输出答案
        for (int i = 2; i <= n; ++i) cout << ans[i] << " \n"[i == n];
    }
    return 0;
}

正确性说明

该 DP 实质上是模拟了逐步构建最优路径的过程。排序保证了当新点加入时，与已有路径中点的边权可以简单表示为 $a_i + b_j$ 或 $a_j + b_i$ 的形式。通过三种状态 $t$ 分别记录路径的端点情况，可以无遗漏地枚举所有可能的路径构造方式。最终答案数组 $ans[k]$ 记录的是所有长度为 $k$ 的路径的最小代价。

示例验证（第一个用例）

输入：

3
0 2
2 1
3 3

排序后为 $(2,1),\;(3,3),\;(0,2)$。运行 DP 得到 $ans[2]=4,\; ans[3]=9$，与题目输出一致。