背景 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 Format
第一行一个整数n
接下来n行，每行两个整数x,y，表示某个点的坐标。
输入中保证没有重复的两点，
保证最西端和最东端都只有一个点。
输出格式 Output Format
一行，即最短回路的长度，保留2位小数。
非常难想到的DP.
f[i][j] 表示第一个人走到第 i 点，第二个人走到第 j 个点。
因为 f[i][j] 与 f[j][i] 轮换对称, 为避免重复， 规定 i 恒大于 j.
若 j+1=i f[i][j]=min(f[1~j-1][j]+dis(1~j-1,j)); f[j][1~j-1] 与 f[1~j-1][j] 对称。
若 j+1<i f[i][j]=f[i-1][j]+dis(i-1,i);
另外 1e24 表示 10的24次方。
1 #include<iostream> 2 #include<math.h> 3 #include<stdio.h> 4 //#include<fstream> 5 using namespace std; 6 //ifstream fin("cin.in"); 7 8 int n; 9 double f[1001][1001]; 10 double d[1001][1001]; 11 double x[1001],y[1001]; 12 13 void Qsort(int left,int right){ 14 if(left>=right) return ; 15 int i=left,j=right;double mid=x[(left+right)>>1]; 16 while(i<=j) 17 { 18 while(x[i]<mid) i++; 19 while(x[j]>mid) j--; 20 if(i<=j) 21 { 22 swap(x[i],x[j]); 23 swap(y[i],y[j]); 24 i++;j--; 25 } 26 } 27 Qsort(left,j); 28 Qsort(i,right); 29 } 30 31 int main() 32 { 33 cin>>n; 34 for(int i=1;i<=n;++i) 35 cin>>x[i]>>y[i]; 36 37 Qsort(1,n); 38 39 for(int i=1;i<=n;++i) 40 for(int j=i+1;j<=n;++j) 41 d[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); 42 43 for(int i=1;i<=n;++i) 44 for(int j=1;j<=n;++j) 45 f[i][j]=1e24; 46 47 f[2][1]=d[1][2]; 48 for(int i=3;i<=n;++i) 49 for(int j=1;j<i;++j) 50 if(j+1<i) f[i][j]=f[i-1][j]+d[i-1][i]; 51 else 52 { 53 for(int k=1;k<j;++k) 54 f[i][j]=min(f[i][j],f[j][k]+d[k][i]); 55 } 56 57 printf("%.2lf\n",f[n][n-1]+d[n-1][n]); 58 return 0; 59 60 }