洛谷OJ P1433 吃奶酪 解题报告

by MedalPluS

题目描述

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

输入描述

第一行一个数n  (n<=15)
接下来每行2个实数，表示第i块奶酪的坐标。
两点之间的距离公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))

输出描述

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

分析

这题很明显就是一个搜索题，枚举一下1_n的全排列，然后从0开始，按照排列一个一个算，时间复杂度O（n!）

这里我们可以发现，如果枚举过程中，当前得到的距离已经大于最少距离，那么就直接退出，这就是个最优性剪枝

然后就可以AC了

笔者在写这题时使用了cin.sync_with_stdio(false)，结果就WA了，后来发现有小数点时不能用这玩意

代码 

1 #include 
     
       2 #include 
      
        3 #include 
       
          4 using namespace std; 5  6 #define rep(i,l,r) for(i=l;i<=r;i++) 7  8 const int maxn=16; 9 const int flag=1e9;10 11 double point[maxn][2],ans=999999999;12 int n;13 bool used[maxn];14 double d[maxn][maxn];15 16 double dis(int x,int y){17     double x1=point[x][0],y1=point[x][1];18     double x2=point[y][0],y2=point[y][1];19     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));20 }21 22 void dfs(int i,double cost,int pos){23     if(i>n){24         if(ans>cost)ans=cost;25         return ;26     }27     if(cost>=ans)return;//best cut 28     int j;29     rep(j,1,n)30       if(!used[j]){31           used[j]=true;32           dfs(i+1,cost+d[pos][j],j);33           used[j]=false;34       }35 }36 37 int main(){38     cin>>n;39     memset(used,false,sizeof(used));40     int i,j;41     rep(i,1,n)42       cin>>point[i][0]>>point[i][1];43     point[0][0]=point[0][1]=0.0;44     rep(i,0,n)45       rep(j,0,n)46         d[i][j]=dis(i,j);47     dfs(1,0,0);48     printf("%.2lf",ans);49     return 0;50 }