洛谷P1433 吃奶酪 题解

题目链接：P1433 吃奶酪

题意：

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

输入格式：

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

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

输出格式：

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

数据范围：

对于全部的测试点，保证 $1\leq n\leq 15$，$|x_i|, |y_i| \leq 200$，小数点后最多有 $3$ 位数字。

提示:

对于两个点 $(x_1,y_1)$，$(x_2, y_2)$，两点之间的距离公式为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

注意到 $n \le 15$ ，考虑状压dp。

显然我们不会重复走到同一个奶酪的位置，因为两点之间线段最短，折线一定不优。

记 $f_{i,j}$ 表示当前在 $i$ ，已经吃过的奶酪的状态的为 $j$ 时的最小花费。转移显然。

时间复杂度 $\mathcal{O}(n^2 2^n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(double &x,double y) { x > y ? x = y : 0; }
#define ctz __builtin_ctz
#define N ((int)(25))
#define M ((int)(4e4+15))
#define sq(x) ((x)*(x))
#define ID(x) (1 << (x-1))

int n,mx;
double res=1e233,a[N][N], x[N], y[N], f[N][M];
double dis(int a,int b)
{ return sqrt(sq(x[a] - x[b]) + sq(y[a] - y[b])); }
#define lowbit(x) ((x) & (-(x)))
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(2);
    cin >> n; mx = (1 << n) - 1;
    for(int i=1; i<=n; i++) cin >> x[i] >> y[i];
    for(int i=1; i<=n; i++) for(int j=1; j<=mx; j++) f[i][j] = 1e18;
    for(int i=0; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            a[j][i] = a[i][j] = dis(i,j);
    for(int i=1; i<=n; i++) f[i][ID(i)] = a[0][i];
    for(int k=0,u,v; k<=mx; k++)
        for(int i = k,r = mx-k; i; i -= lowbit(i))
            for(int j = r; j; j -= lowbit(j))
            {
                u = ctz(lowbit(i)) + 1, v = ctz(lowbit(j)) + 1;
                down(f[v][k | ID(v)], f[u][k] + a[u][v]);
            }
    for(int i=1; i<=n; i++) down(res, f[i][mx]);
    cout << res << '\n';
    return 0;
}