3759 - 旅行商简化版
背景 Background
欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解，但是有办法在多项式时间内求出一个较优解。
为了简化问题，而且保证能在多项式时间内求出最优解，J.L.Bentley提出了一种叫做bitonic tour的哈密尔顿环游。它的要求是任意两点(a,b)之间的相互到达的代价dist(a,b)=dist(b,a)且任意两点之间可以相互到达，并且环游的路线只能是从最西端单向到最东端，再单项返回最西端，并且是一个哈密尔顿回路。
描述 Description
著名的NPC难题的简化版本
现在笛卡尔平面上有n(n<=1000)个点，每个点的坐标为(x,y)(-2^31<x,y<2^31，且为整数)，任意两点之间相互到达的代价为这两点的欧几里德距离，现要你编程求出最短bitonic tour。
Input
第一行一个整数n
接下来n行，每行两个整数x,y，表示某个点的坐标。
输入中保证没有重复的两点，
保证最西端和最东端都只有一个点。
Output
一行，即最短回路的长度，保留2位小数。
Examples
Input
7 0 6 1 0 2 3 5 4 6 1 7 5 8 2
Output
25.58
Solution C++
#include<iostream> #include<math.h> #include<stdio.h> //#include<fstream> using namespace std; //ifstream fin("cin.in"); int n; double f[1001][1001]; double d[1001][1001]; double x[1001],y[1001]; void Qsort(int left,int right){ if(left>=right) return ; int i=left,j=right;double mid=x[(left+right)>>1]; while(i<=j) { while(x[i]<mid) i++; while(x[j]>mid) j--; if(i<=j) { swap(x[i],x[j]); swap(y[i],y[j]); i++;j--; } } Qsort(left,j); Qsort(i,right); } int main() { cin>>n; for(int i=1;i<=n;++i) cin>>x[i]>>y[i]; Qsort(1,n); for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) d[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) f[i][j]=1e24; f[2][1]=d[1][2]; for(int i=3;i<=n;++i) for(int j=1;j<i;++j) if(j+1<i) f[i][j]=f[i-1][j]+d[i-1][i]; else { for(int k=1;k<j;++k) f[i][j]=min(f[i][j],f[j][k]+d[k][i]); } printf("%.2lf\n",f[n][n-1]+d[n-1][n]); return 0; }