本文共 825 字，大约阅读时间需要 2 分钟。
房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0) 点处。
第一行有一个整数，表示奶酪的数量 n。
第 2 到第 (n + 1) 行，每行两个实数，第 (i + 1) 行的实数分别表示第 i 块奶酪的横纵坐标 x_i, y_i
输出一行一个实数，表示要跑的最少距离，保留 2 位小数。
41 11 -1-1 1-1 -1
7.41
这道题，我们分析数据：1<=n<=15。所以 《 很 显 然 》，这道题是用状压DP，动转移方程如下
： f [ i ] [ k ] = m i n ( f [ i ] [ k ] , f [ j ] [ k − ( 1 < < i − 1 ) ] + h h ( i , j ) ) f[i][k]=min(f[i][k],f[j][k-(1<<i-1)]+hh(i,j)) f[i][k]=min(f[i][k],f[j][k−(1<<i−1)]+hh(i,j)) 然后进行几个特判，赋个初值，就差不多了#include#include #include using namespace std;int n; double x[20],y[20];double f[30][1<<15],ans=0x3f3f3f3f;double hh(int i,int j){ return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}int main(){ cin>>n; for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]); for(int i=1;i<=n;i++) for(int j=1;j<(1<
转载地址：http://pghl.baihongyu.com/