题解 | #收集纸片#

这是一个典型的旅行商问题（TSP）变种，需要从起点出发，访问所有目标点（纸片）后返回起点，且只能沿坐标轴方向移动（曼哈顿距离）。由于纸片数量 ，数据规模很小，适合使用状态压缩动态规划（DP + Bitmask）进行精确求解。

核心观察：

• 两点间最短距离为曼哈顿距离：
• 访问顺序影响总距离，需要找到最优排列
• 时，，状态总数可控

算法步骤

1. 预处理距离

• 计算起点到每个纸片的距离
• 计算纸片两两之间的距离
• 这些距离在DP过程中会重复使用

2. 状态设计

• 状态掩码：用二进制位掩码 表示已收集的纸片集合（第 位为1表示第 个纸片已收集）
• DP表定义： 表示在已收集 对应纸片集合、当前位于第 个纸片位置时的最短路径长度

3. 初始化

• 对于每个纸片 （从0开始编号）：
  • （从起点直接到该纸片的距离）

4. 状态转移

• 遍历所有状态 （从 到 ）
• 对于每个可能的当前位置 （满足 的第 位为1）
  • 对于每个未访问的纸片 （满足 的第 位为0）：
    • 转移方程：
      

5. 计算最终答案

• 收集完所有纸片后（），需要返回起点：
  

6. 输出

• 按格式输出：The shortest path has length X

计算复杂度分析

时间复杂度：

• 状态数：
• 每个状态需尝试转移到 个未访问点
• 总复杂度：
• 当 时： 次运算，远低于1秒限制

空间复杂度：

• 需存储 数组，大小为
• 空间复杂度：
• 当 时： 个整数，远小于256MB限制

预处理复杂度：

• 距离计算：，可忽略不计

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;

const ll INF = 1e18;

void solve() {
    int n;
    int m1, m2;
    cin >> m1 >> m2;
    pi start;
    cin >> start.first >> start.second;
    cin >> n;
    vector<pi> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i].first >> p[i].second;

    auto compute = [](const pi & a, const pi & b) -> int {
        return abs(a.first - b.first) + abs(a.second - b.second);
    };
    // 预处理
    vector<int> d1(n);
    vector<vector<int>> d2(n, vector<int>(n, m1 + m2 + 10));

    for (int i = 0; i < n; i++) {
        d1[i] = compute(start, p[i]);
        for (int j = i; j < n; j++) {
            if (i == j)
                d2[i][j] = 0;
            else {
                d2[i][j] = compute(p[i], p[j]);
                d2[j][i] = d2[i][j];
            }
        }
    }

    vector<vector<ll>> dp((1 << n), vector<ll>(n, INF));
    // 初始化从起点直接到该纸片的距离
    for (int i = 0; i < n; i++) {
        dp[(1 << i)][i] = d1[i];
    }

  	// 状态压缩动态规划
    for (long long mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0)
                continue;
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) == 0) {
                    dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + d2[i][j]);
                }
            }
        }
    }

    ll ans = INF;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[(1 << n) - 1][i] + d1[i]);
    }
    cout << "The shortest path has length " << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}