LuoguP1433 吃奶酪

题目描述

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

输入格式

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

第22到第(n+1)(n+1)行，每行两个实数，第(i+1)(i+1)行的实数分别表示第ii块奶酪的横纵坐标xi,yixi,yi​。

输出格式

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

样例#1

输入：　　　　　　　　　输出：7.41　　　　　　　　　　
4　　　　　　　　　　　
1 1
1 -1
-1 1
-1 -1

数据规模

对于全部的测试点，保证1≤n≤15;|xi|,|yi|≤2001≤n≤15;|xi|,|yi|≤200,小数点后最多有33位数字。

提示：

对于两个点(x1,y1),(x2,y2)(x1,y1),(x2,y2)，两点间距离公式为(x1−x2)2+(y1−y2)2−−−−−−−−−−−−−−−−−−√(x1−x2)2+(y1−y2)2 。

思路：

首先这个题第一眼看上去就是个搜索，然后噼里啪啦一顿打完以后发现过不了(T了一个点）。

然后就考虑有没有别的更高效的办法。一般来说，DP能做的题搜索都可以做，所以我就考虑能不能用DP来解决这个题。

实际上是可以的。我们可以考虑用状压DP来解决。

设f[i][j]f[i][j]为当前走到ii这个点，走过jj这个集合中的点后所走的最短路径（ii包括在jj中）。

怎么转移呢？很明显我们需要枚举每种可能的jj，然后再枚举当前jj中所有可能的ii，然后再枚举ii这个点是从哪里走过来的，就可以完成转移。

具体思路就这些，还有需要注意的就是此题输入的xixi和yiyi可能出现小数。

Code：

#include
#include
#include
#include
#include
int n;
double x[20], y[20];
double f[20][65536];
double dis[20][20];
inline double Length(double dx1,double dy1,double dx2,double dy2){return std::sqrt((dx1 - dx2) * (dx1 - dx2) + (dy1 - dy2) * (dy1 - dy2));
}
inline double _min(double x, double y) { return x < y ? x : y; }
int main(){scanf("%d", &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 <= n;++j){if(i==j) dis[i][j] = 0;else dis[i][j] = Length(x[i], y[i], x[j], y[j]);}}memset(f, 127, sizeof(f));for (int i = 1; i < (1 << n);++i){for (int j = 1; j <= n;++j){if(((i>>(j-1))&1)==0) continue;//判断当前点是否在集合中if(i==(1<<(j-1))){//判断当前集合中是否只有这一个点f[j][i] = 0;continue;}for (int k = 1; k <= n;++k){if(((i>>(k-1))&1)==0) continue;//判断当前点是否在集合中if(j==k) continue;f[j][i] = _min(f[j][i], f[k][i - (1 << (j - 1))] + dis[k][j]);//转移，f[k][i - (1 << (j - 1))]表示的就是走到k时的最短距离}}}double res = -12;for (int i = 1; i <= n;++i){double ot = f[i][(1 << n) - 1] + Length(0, 0, x[i], y[i]);//不要忘了加上到（0,0）点的距离if(res==-12||res>ot) res = ot;}printf("%.2lf\n", res);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！