UVA 1347"Tour"（经典DP）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e3+50;
 4 
 5 int n;
 6 struct Point
 7 {
 8     int x,y;
 9     bool operator < (const Point& obj) const
10     {
11         return x < obj.x;
12     }
13 }p[maxn];
14 ///dp[i][j]:前i个点全部走过，并且一个人在i点，一个人在j点
15 ///从(i,j)状态到n点所需的最短距离
16 double dp[maxn][maxn];
17 
18 double d(int a,int b)
19 {
20     return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
21 }
22 
23 double Solve()
24 {
25     for(int i=1;i < n-1;++i)///预处理处dp[n-1][1,...,n-2]
26         dp[n-1][i]=d(n-1,n)+d(i,n);
27     for(int i=n-2;i >= 1;--i)
28         for(int j=i-1;j >= 1;--j)
29             dp[i][j]=min(dp[i+1][j]+d(i,i+1),dp[i+1][i]+d(j,i+1));
30 
31     return d(1,2)+dp[2][1];
32 }
33 int main()
34 {
35     while(~scanf("%d",&n))
36     {
37         for(int i=1;i <= n;++i)
38             scanf("%d%d",&p[i].x,&p[i].y);
39         sort(p+1,p+n+1);
40         printf("%.2f\n",Solve());
41     }
42     return 0;
43 }