题解【洛谷P1433】吃奶酪

题面

看到数据范围那么小，一眼状压\(\text{DP}\)。

设\(dp[i][s]\)表示从\(i\)出发，走过的点的集合为\(s\)的最小距离。

不难推出转移方程（\(dis(i,j)\)为\(i\)点到\(j\)点的距离）：

\[dp[i][s] = \min(dp[i][s], dp[j][s - (1 << (i - 1))] + dis(i,j))\]

边界：

\[dp[i][1 << (i - 1)] = 0\]

代码实现：

#include <bits/stdc++.h>
#define itn int
#define gI gi

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

int n;
double x[20], y[20], dis[20][20], ans = 1000000000.0, dp[20][1 << 16];

inline double getjuli(double x, double y, double xx, double yy)
{
    return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));
}

int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    n = gi();
    for (int i = 1; i <= n; i+=1) scanf("%lf %lf", &x[i], &y[i]);
    for (int i = 1; i <= n; i+=1)
        for (int j = 1; j <= n; j+=1)
            dis[i][j] = getjuli(x[i], y[i], x[j], y[j]);//预处理出两点间的距离
    memset(dp, 127, sizeof(dp));
    for (int s = 1; s <= (1 << n) - 1; s+=1)
    {
        for (int i = 1; i <= n; i+=1)
        {
            if (!(s & (1 << (i - 1)))) continue;
            if (s == (1 << (i - 1))) {dp[i][s] = 0; continue;}//边界
            for (int j = 1; j <= n; j+=1)
            {
                if ((!s & (1 << (j - 1))) || i == j) continue;
                dp[i][s] = min(dp[i][s], dp[j][s - (1 << (i - 1))] + dis[i][j]);//转移
            }
        }
    }
    for (int i = 1; i <= n; i+=1)
    {
        double ss = dp[i][(1 << n) - 1] + getjuli(0, 0, x[i], y[i]);//注意加上到点(0,0)的距离
        if (ss < ans) ans = ss; 
    }
    printf("%.2lf\n", ans);
    return 0;
}

题解【洛谷P1433】吃奶酪

原文：https://www.cnblogs.com/xsl19/p/12251315.html