题面

题目描述

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

输入输出格式

输入格式

第一行一个正整数 (n)。接下来每行 (2) 个实数，表示第i块奶酪的坐标。两点之间的距离公式为 (sqrt{(x_1-x_2)^2+(y_1-y_2)^2})。

输出格式

一个数，表示要跑的最少距离，保留 (2) 位小数。

输入输出样例

输入样例 #1

输出样例 #1

7.41

说明

(1leq nleq 15)。

分析

数据范围暴露一切：这道题用状压dp。
这道题的状压dp过于简单，我并不想多说，，

代码

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2020-02-22 23:12:58 
 * @Last Modified by:   crab-in-the-northeast 
 * @Last Modified time: 2020-02-22 23:12:58  
 */
//插件出锅了……Last Modified time应该是2020-02-23 00:58分钟左右，不知道他咋想的，，
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#undef y1

int n;
const int maxn = 25;
double dp[25][40005];

struct cheese {
    double x;
    double y;
}a[maxn];

double getdis(double x1,double y1,double x2,double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double min(double a,double b) {
    return a < b ? a : b;
}

int main() {
    memset(dp,127,sizeof(dp));//初始化dp为无穷大（memset小技巧）
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%lf %lf",&a[i].x,&a[i].y);

    for(int s = 1; s <= (1 << n) - 1; s++) {
        for(int i = 1; i <= n; i++) {
            if(s & (1 << (i - 1))) {
                if(s == (1 << (i-1))) {
                        dp[i][s] = 0;
                        continue;
                }
                for(int j = 1; j <= n; j++) {
                    if(i != j && s & (1 << (j - 1))) {
                        dp[i][s] = min(dp[i][s],dp[j][s - (1 << (i - 1))] + getdis(a[i].x,a[i].y,a[j].x,a[j].y));
                    }
                }
            }
        }
    }
    //以上都是状压板子，这里不多说。

    double ans = 1008610086;
    for(int i = 1; i <= n; i++) ans = min(ans,dp[i][(1 << n) - 1]+getdis(a[i].x,a[i].y,a[0].x,a[0].y));
    printf("%.2lf
",ans);
    return 0;
    //好吧算下来我好想啥都没说……
}

评测结果

AC 100：R30954388