题目
luogu P1433 吃奶酪
思路
状态表示
每个点的位置上，0 位还未走过，1 位已经走过，这样可以压缩当前的遍历状态
记f[i][j]为在第 i 点在 j 状态时走过的最小路程
状态转移
死活想不出来的状态转移方程
给出二进制状态 j，终点为 i，起点为 k，得状态转移方程f[i][j] = min(f[i][j], f[k][j-(1<<(i-1))] + distance(i, k))
解释一下f[k][j-(1<<(i-1))]，将状态 j 中的第 i 个点去掉所经过的最小路程
这里相当于枚举了对于当前状态的上一种状态的所有可能，然后统计出最小路径，进行下一步的转移
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#define ll long long
using namespace std;
// 状压dp
int n;
double p[20][2];
double dp[20][1 << 15]; // 状态压缩
// dp[i][j] i 点时状态为 j 时经过的最小路程
double ans = 1e9;
// 状态转移方程？
double distance(double a[], double b[]) {
return sqrt((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));
}
int main() {
ios::sync_with_stdio(0);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
memset(dp, 127, sizeof(dp)); // 这样可以给浮点数赋值无穷大
for (int i = 1; i <= n; i++) {
cin >> p[i][0] >> p[i][1];
dp[i][1 << (i - 1)] = distance(p[i], p[0]);
}
// 三层循环 状态 当前起点 可能到达点
for (int j = 1; j <= (1 << n); j++)
for (int i = 1; i <= n; i++) {
if ((j & (1 << (i - 1))) == 0) // 判断状态中第i位是否被包含
continue;
for (int k = 1; k <= n; k++) {
if (i == k)
continue;
if (j & (1 << (i - 1)) == 0)
continue;
dp[i][j] = min(
dp[i][j], dp[k][j - (1 << (i - 1))] + distance(p[i], p[k]));
}
}
for (int i = 1; i <= n; i++)
ans = min(ans, dp[i][(1 << n) - 1]);
cout << fixed << setprecision(2) << ans;
return 0;
}
|
