背景 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 }
