Luogu-P1433-吃奶酪

Posted on Edited on Word count in article: 715

题目 P1433 吃奶酪

题目描述

房间里放着 $n$ 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 $(0,0)$ 点处。

输入格式

第一行有一个整数，表示奶酪的数量 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行两个实数，第 $(i + 1)$ 行的实数分别表示第 $i$ 块奶酪的横纵坐标 $x_i, y_i$。

输出格式

输出一行一个实数，表示要跑的最少距离，保留 $2$ 位小数。

思路：状态压缩dp（状压dp）

使用状压dp原因

  • 数据量小（$n \leq 15$）
  • 可以使用一个整数表达一个访问过的点的集合

基本定义

将访问过的数（$a, b, c, \cdots $）定义为状态 $state=2^a+2^b+2^c+\cdots$，定义第 $i$ 个点到第 $j$ 个点的距离为 $dis(i, j)$。

1
state = (1 << a) + (1 << b) + (1 << c) + ...

dp表

$dp[i][state]\rightarrow$ 访问过状态为 $state$ 的点之后，到达第 $i$ 个点的最小距离（$0 \leq i \leq n,1 \leq state \leq 2^{n + 1}-1$）。说明：将原点看成第 $0$ 个点，所以 $i$ 可以取 $0$，$state$ 的有效值仅为奇数（必定过原点），当 $0 \sim n$ 位全部为 $1$ 时取最大值 $2^{n + 1}-1$。

状态

  • 初状态：原点到所有点的距离为确定值。

    1
    dp[i][1] = dis(i, 0);

  • 状态转移方程：从小到大遍历 $state$，以未经过的点 $j$ 开始（虽然不判断点$j$是否经过也能AC），向未经过的点 $i$ 走。

    1
    dp[i][state | (1 << j)] = min(dp[i][state | (1 << j)], dis(i, j) + dp[j][state]);

  • 末状态：在所有的 $i$ 中，选出结果最小的。

    1
    2
    const int all_vis_state = (1 << (n + 1)) - 1;
    ans = min(ans, dp[i][all_vis_state - (1 << i)]);

AC Code

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
61
62
63
64
65
66
67
68
69
70
// template v7
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void minset(double &t, double other) {
    t = min(t, other);
}

inline void maxset(double &t, double other) {
    t = max(t, other);
}

struct pos {
    double x, y;
};

const int inf = 0x7f7f7f7f;

const int N = 17;

int n;

pos p[N];

double dp[N][1 << N];

inline double sq(double d){
    return d * d;
}

inline double dis(int from, int to){
    return sqrt(sq(p[from].x - p[to].x) + sq(p[from].y - p[to].y));
}

inline bool vis(int state, int target){
    return (state & (1 << target));
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    memset(dp, inf, sizeof dp);
    for(int i = 1; i <= n; i++) {
        dp[i][1] = dis(0, i);
    }
    for(int state = 1; state < (1 << (n + 1)); state += 2){
        for(int i = 1; i <= n; i++) {
            if(!vis(state, i)){
                for(int j = 0; j <= n; j++) {
                    if(i == j) continue;
                    if(vis(state, j)) continue;
                        minset(dp[i][state | (1 << j)], dis(i, j) + dp[j][state]);
                        // cout << dp[i][state | (1 << j)] << endl;
                }
            }
        }
    }
    double minv = inf;
    const int all_vis_state = (1 << (n + 1)) - 1;
    for(int i = 1; i <= n + 1; i++){
        int c_state = all_vis_state - (1 << i);
        minset(minv, dp[i][c_state]);
    }
    cout << fixed << setprecision(2) << minv << endl;
    return 0;
}

补充

保留两位小数的两种做法

  • printf("%.2lf", x);
  • cout << fixed << setprecision(2) << x;