Loading... # 洛谷 P1433 吃奶酪 题解 ## 题目描述 房间里放着 $n$ 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 $(0,0)$ 点处。 ## 输入 第一行有一个整数，表示奶酪的数量 $n$。 第 $2$ 到第 $(n + 1)$ 行，每行两个实数，第 $(i + 1)$ 行的实数分别表示第 $i$ 块奶酪的横纵坐标 $x_i, y_i$。 ## 输出格式 输出一行一个实数，表示要跑的最少距离，保留 $2$ 位小数。 ## 解题思路 本题首先考虑DFS的方式解题： - `dfs(u, state， d)`表示为当前搜索到了点`u`， 目前状态为`state`， 目前走过的距离为`d` - `state`为状态压缩量， 第`i`位表示第`i`个点是否已经走到， 走到了为`1`， 否则为`0` - 如果当前状态为`(1<<n) - 1`， 则证明所有节点都已经遍历到， 此时应该更新`ans` 首先不难发现， 在不考虑剪枝的情况下， 最大的搜索次数可能是$15!$， 一定会TLE, 所以需要考虑优化搜索 ### 剪枝 首先最先想到的应该是剪枝思路， 对于这个问题可以有以下三个剪枝方案 - 减小搜索冗余 - 为了减小重复搜索， 需要额外开一个数组`dp[u][state]`表示当前搜索到第`u`个节点， 状态为`state`(即已经搜索到了`state`中搜到的点)时走过的最小的距离 - 最优性剪枝 - 如果当前走过的距离已经大于等于最小距离， 则一定不可行 - 设当前已经搜索到节点`u`， 当前状态为`state`， 接下来要搜索节点`i`，如果`dp[i][state + (1 << (i - 1))]`已经有值， 并且这个值要比当前搜索到的距离`d`加上从节点`u`到节点`i`的距离`dist[u][i]`小， 则提前结束搜索 #### AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <cmath> #include <iomanip> #define endl '\n' using namespace std; const int N = 20, M = 1 << 16; typedef pair<double, double> PDD; int n; PDD a[N]; double dist[N][N]; double dp[N][M]; double ans = 1e9 + 7; void init() { for(int i = 0; i <= n; i ++) { for(int j = 1; j <= n; j ++) { double x1 = a[i].first, y1 = a[i].second; double x2 = a[j].first, y2 = a[j].second; double dx = abs(x2 - x1), dy = abs(y1 - y2); dist[i][j] = sqrt(dx * dx + dy * dy); } } } void dfs(int u, int state, double d) { if(d >= ans) return ; if(state == ((1 << n) - 1)) { ans = min(ans, d); } for(int i = 1; i <= n; i ++) { if((state >> (i - 1)) & 1) continue; double& t = dp[i][state + (1 << (i - 1))]; if(abs(t - 0) > 1e-6 && t - d - dist[u][i] <= 0) continue; t = d + dist[u][i]; dfs(i, state + (1 << (i - 1)), d + dist[u][i]); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n; i ++) { double x, y; cin >> x >> y; a[i] = {x, y}; } init(); dfs(0, 0, 0); cout << fixed << setprecision(2) << ans << endl; return 0; } ``` ### 状压DP 本题可以使用状态压缩的思路来解决 - 状态表示: `dp[u][state]` - 集合：当前在第`i`个节点， 当前走过的节点对应的状态为`state`的所有路径的集合 - 属性：集合中所有路径的最小值 - 状态计算 - 设`k`节点对应的位置在`state`中出现， 则有`dp[u][state] = min(dp[u][state], dp[k][state - 1 << i] + dist[k][u])` #### AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <cmath> #include <iomanip> #define endl '\n' using namespace std; const int N = 20, M = 1 << 16; typedef pair<double, double> PDD; int n; PDD a[N]; double dist[N][N]; double dp[N][M]; bool st[N][M]; int dic[M]; double ans = 0; int lowbit(int x) { return x & -x; } void init() { memset(dp, 127, sizeof dp); for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { double x1 = a[i].first, y1 = a[i].second; double x2 = a[j].first, y2 = a[j].second; double dx = abs(x2 - x1), dy = abs(y1 - y2); dist[i][j] = sqrt(dx * dx + dy * dy); } } for(int i = 0; i < n; i ++) dp[i][1 << i] = sqrt(a[i].first * a[i].first + a[i].second * a[i].second); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n; i ++) { double x, y; cin >> x >> y; a[i] = {x, y}; } init(); for(int j = 0; j < (1 << n); j ++) { for(int i = 0; i < n; i ++) { if(((j >> i) & 1) == 0) continue; for(int k = 0; k < n; k ++) { if(((j >> k) & 1) == 0 || i == k) continue; dp[i][j] = min(dp[i][j], dp[k][j - (1 << i)] + dist[k][i]); } } } double ans = 1e9 + 7; for(int i = 0; i < n; i ++) ans = min(ans, dp[i][(1 << n) - 1]); cout << fixed << setprecision(2) << ans << endl; return 0; } ``` ### 记忆化搜索 本题还可以用记忆化搜索的思路解答：可以发现DFS会超时的原因是搜索到了很多的重复状态， 因此可以用记忆化搜索的思想，将已经搜索到的答案记录下来， 减少重复搜索， 从而提高搜索效率 设`dp[u][state]`表示由当前节点走完所有的节点所需要的最小的路径长度， 则可以采用DFS搜索的方式动态更新数组 - 如果`state==（1 << n ) - 1`, 又因为当前已经遍历完所有的节点， 因此对于任意$i \in [1, n]$都有`dp[i][state] == 0` - 如果当前`dp[u][state] != 0`， 则证明当前的`dp[u][state]`已经得到了最小值， 此时应该直接返回 - 否则则搜索最小值， 用最小值赋值`dp[u][state]`并返回最小值 #### AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <cmath> #include <iomanip> #define endl '\n' using namespace std; const int N = 20, M = 1 << 16; typedef pair<double, double> PDD; int n; PDD a[N]; double dist[N][N]; double dp[N][M]; double ans = 1e9 + 7; void init() { for(int i = 0; i <= n; i ++) { for(int j = 1; j <= n; j ++) { double x1 = a[i].first, y1 = a[i].second; double x2 = a[j].first, y2 = a[j].second; double dx = abs(x2 - x1), dy = abs(y1 - y2); dist[i][j] = sqrt(dx * dx + dy * dy); } } } double dfs(int u, int state) { if(state == (1 << n) - 1) return 0; if(dp[u][state] != 0) return dp[u][state]; double tmp = 1e9; for(int i = 1; i <= n; i ++) { if((state >> (i - 1)) & 1) continue; int new_state = state + (1 << (i - 1)); tmp = min(tmp, dist[u][i] + dfs(i, new_state)); } dp[u][state] = tmp; return tmp; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n; i ++) { double x, y; cin >> x >> y; a[i] = {x, y}; } init(); ans = dfs(0, 0); cout << fixed << setprecision(2) << ans << endl; return 0; } ``` 最后修改：2025 年 03 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏