当前位置：首页 > news >正文

洛谷P1433 吃奶酪状压dp解法

news 2026/5/26 21:32:19

https://www.luogu.com.cn/problem/P1433

题目意思

在平面直角坐标系中，小老鼠一开始在原点 (0,0)。有 n 块奶酪，坐标已知。小老鼠要把所有奶酪都吃掉，问最少要跑多少距离？

n ≤ 15，坐标绝对值不超过 200，保留两位小数。

题目分析

假设奶酪编号 1~4。考虑两条不同的路径：

路径A：0 → 1 → 2 → 3，现在在 3，已经吃了 {1,2,3}
路径B：0 → 2 → 1 → 3，现在也在 3，已经吃了 {1,2,3}

这两条路径到达了完全相同的局面：当前位置相同，已经吃掉的奶酪集合相同。接下来的任务也一样：从 3 出发，吃掉剩下的 {4}。

如果我们在 DFS 中能“记住”这个局面的最优解，就不用反复计算了。这就是记忆化搜索的思想。

Hint1：二进制表示已经吃掉的集合(状压思想)

奶酪数量很少（≤15），我们可以用一个二进制数表示集合。

一共有 n 个奶酪，用 n 个二进制位表示。
从右往左，第 i 位为 1 表示第 i 块奶酪已经吃了，0 表示没吃。

例子：n = 4，二进制 0101（十进制 5）表示 {奶酪1, 奶酪3} 已吃。

这种用二进制表示状态的方法，称为状态压缩（状压）。

常用位运算 (1-base) ：

1 << (i-1) ：只选中第 i 个奶酪（注意第 i 个对应从右数第 i 位，左移 i-1 位）
mask | (1 << (i-1)) ：把第 i 个奶酪加入集合
mask & (1 << (i-1)) ：检查第 i 个奶酪是否在集合中
全集：(1 << n) - 1（n 个 1）

Hint2: 推出DP状态转移

设 dp[mask][i] 表示：
已经吃掉的奶酪集合为 mask，并且最后停在奶酪 i 时，所走过的最短总距离。

所以我们要的最终答案为：min( dp[全集][i] ) ，即吃完所有奶酪时，无论最后停在哪块，取最小值。

状态转移

我们需要从“小集合”递推到“大集合”。

初始化：从起点 0 直接去第一块奶酪 i
dp[ 1<<(i-1) ][i] = dist(0, i)
递推：枚举每个集合 mask，枚举当前所在点 i（必须在 mask 中）
再枚举下一个要吃的奶酪 j（必须不在 mask 中）
则新集合 nxt = mask | (1<<(j-1))
dp[nxt][j] = min(dp[nxt][j], dp[mask][i] + dist[i][j])
由于 nxt 一定比 mask 大（集合中多了一个 1），所以我们按照 mask 从小到大的顺序遍历就没有后效性。

代码实现

//
// Created by awake on 2026/5/26.
// 状压dp实际是正向的记忆化搜索
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)// NOLINT
// #define int long long
using pdd = pair<double, double>; //NOLINT
using ll = long long;             //NOLINT
template <typename T>
using vec = vector<T>; //NOLINT// #define endl '\n'
constexpr int INF = 0x3f3f3f3f;void solve()
{int n;cin >> n;vec<pdd> P(n + 1);P[0] = {0, 0};for (int i = 1; i <= n; i++)cin >> P[i].first >> P[i].second;vec dist(n + 1, vec<double>(n + 1));for (int i = 0; i <= n; i++)for (int j = 0; j <= n; j++)dist[i][j] = hypot(P[i].first - P[j].first, P[i].second - P[j].second);const int MX = 1 << n;vec dp(MX, vec<double>(n + 1, INF));for (int i = 1; i <= n; i++)dp[1 << (i - 1)][i] = dist[0][i];for (int mask = 1; mask < MX; mask++){for (int i = 1; i <= n; i++){if (!(mask & (1 << (i - 1))))continue;for (int j = 1; j <= n; j++){if (mask & (1 << (j - 1)))continue;int nxt = mask | (1 << (j - 1));dp[nxt][j] = min(dp[nxt][j], dp[mask][i] + dist[i][j]);}}}double ans = INF;for (int i = 1; i <= n; i++)ans = min(dp[MX - 1][i], ans);cout << fixed << setprecision(2) << ans << endl;
}signed main()
{IOS;int T = 1;// cin >> T;while (T--)solve();return 0;
}