Description

給定平面上n個點，設計一條路線，從最左邊的點出發，走到最右邊的點在走回來，除了最左邊的點，其他每個點恰好經過一次，且是的路徑總長最短。兩點之間的路徑長度為歐幾里得距離（就是直線距離）。

Input

第一行一個整數n表示點數，后面n行，每行兩個小數表示點的坐標。

Output

一個小數表示最短的路徑總長，答案保留4位小數。

Sample Input

5
10 10
2 8
1 2
10 6
2 5

Sample Output

29.5535

Data Constraint

對于40%數據n<=100
?對于100%數據n<=5000

Solution

• 這道題的關鍵就是如何處理來回走、且走的點不重復的問題。

• 于是可以巧妙的改成：兩個人同時從最左點出發，沿著兩條不同的路徑走，最后都到達最右點，

• 且除了起點和終點外其余每個點恰好被一個人經過。

• 則設出DP狀態： F[i][j] 表示從 1 到 Max(i,j) 都已被走過、且不重復的最小距離。

• 那么走出下一步（倒著做）， F[i][j] 可以由 F[i+1][j] 和 F[i][j+1] 轉移過來。

• 由于兩個人是完全相同的，所以強制 i>j ， 則有： F[i][j]=F[j][i]

• 于是 F[i][j] 就由 F[i+1][j] 和 F[i+1][i] 轉移過來。

• 且邊界是： F[n?1][j]=dist[n?1][n]+dist[j][n] （直接 i,j 各走一步到終點即可）

• 那么答案就是： dist[1][2]+F[2][1] 。

• （因為第一步是 i 走到了第二個點，根據定義就是 F[2][1] ）

• 這樣時間復雜度就是 O(N2)，注意空間問題（開滾動數組解決）和精度問題（開 double 解決）。

Code

#include<cstdio> #include<cmath> using namespace std; const int N=5001; struct data {double x,y; }a[N]; int n,roll; double f[2][N]; inline double get(int x,int y) {return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y)); } inline double min(double x,double y) {return x<y?x:y; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);for(int i=1;i<n-1;i++) f[0][i]=get(n-1,n)+get(i,n);for(int i=n-2;i>1;i--){roll^=1;for(int j=1;j<i;j++)f[roll][j]=min(f[roll^1][j]+get(i,i+1),f[roll^1][i]+get(j,i+1));}printf("%.4lf",f[roll][1]+get(1,2));return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5268. 旅行的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。