洛谷 P1433 吃奶酪(记忆化)

时间：2021-06-02 21:00:56

题目描述

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

输入输出格式

输入格式：

第一行一个数n (n<=15)

接下来每行2个实数，表示第i块奶酪的坐标。

两点之间的距离公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))


输出格式：

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

输入输出样例

输入样例#1： 
4

1 1

1 -1

-1 1

-1 -1
输出样例#1： 
7.41
解题思路:
记忆化搜索,看代码(注释)
AC代码:
 #include<cstdio>

 #include<cmath>

 #define min(a,b) a<b?a:b

 using namespace std;

 int n;

 double f[][];

 double x[],y[],ans = 999999999999.0;//要求最小值,将答案初始化很大很大

 bool v[];

 void dfs(int s,int now,double l) {

     if(l > ans) return ;//剪枝,如果没有会TLE,如果当前路径已经比答案大,那么不能是最优解了,直接返回

     if(s == n) {//走完n个点

         ans = min(ans,l);//更新答案

         return ;

     }

     for(int i=;i<=n;i++) //枚举所有点

           if(!v[i]) {//没走过

             v[i]=; //标记

             dfs(s+,i,l+f[now][i]);

             v[i]=;  //回溯

         }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i = ;i <= n; i++)

         scanf("%lf%lf",&x[i],&y[i]);

     x[] = ;y[] = ;

     for(int i = ;i <= n; i++)

         for(int j = ;j <= n; j++)

             f[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));//预处理两点的距离

     dfs(,,0.0);//已走过0个点  上一个点是第0个点  已走了长0.0的路径

     printf("%.2lf",ans);

     return ;

 }


 




相关文章