題意：給你一個平面上的點集（x值各不相等），問你從最左邊走到最右邊（只能以x遞增的順序），再從最右邊回到最左邊（以x遞減的順序）問你最短距離是多少。
解題思路：dp[i][j] 表示 其中一條路已經到了 i ?另一條路 在j 的最短距離。
解題代碼：
1 // File Name: c.1.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月17日 星期二 09時15分20秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 int t,n; 28 struct point{ 29 int x, y ; 30 }p[555]; 31 double dp[555][555]; 32 double dis(int a, int b) 33 { 34 return sqrt(1.0*(p[a].x - p[b].x) *(p[a].x -p[b].x) + 1.0*(p[a].y - p[b].y)*(p[a].y -p[b].y)); 35 } 36 int main(){ 37 scanf("%d",&t); 38 while(t--) 39 { 40 scanf("%d",&n); 41 for(int i = 1;i <= n;i ++) 42 { 43 scanf("%d %d",&p[i].x,&p[i].y); 44 } 45 if(n == 1) 46 { 47 printf("%f",0.0); 48 continue; 49 } 50 dp[2][1] = dis(1,2); 51 for(int i = 2;i < n;i ++) 52 { 53 dp[i+1][i] = 100000000; 54 for(int j = 1; j < i ;j ++) 55 { 56 dp[i+1][j] = dp[i][j] + dis(i,i+1); 57 dp[i+1][i] = min(dp[i+1][i],dp[i][j] + dis(j,i+1)); 58 } 59 } 60 printf("%f\n",dp[n][n-1] + dis(n,n-1)); 61 } 62 return 0; 63 }
?
)
