1347 - Tour （雙調歐幾裡得旅行商問題）

鏈接：1347 - Tour

沒想通，看了題解，學習了。。。

J.L. Bentley 建議通過只考慮雙調旅程(bitonic tour)來簡化問題,這種旅程即為從最左點開始，嚴格地從左到右直至最右點，然後嚴格地從右到左直至出發點。下圖(b)顯示了同樣的7個點的最短雙調路線。在這種情況下，多項式的算法是可能的。事實上，存在確定的最優雙調路線的O(n*n)時間的算法。

圖a 圖b<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+16I61NrSu7j2taXOu9WkJiMyNjY4NDvJz8/Uyr61xMa9w+bJz7XExt+49rXjoaMgYSnX7rbMsdW6z8K3z98ss6S2yLTz1LzKxzI0Ljg5oaPV4rj2wrfP37K7ysfLq7X3tcSho2Ipz+DNrLXjtcS8r7rPyc+1xNfutszLq7X3sdW6z8K3z9+ho7Oktsi089S8yscyNS41OKGjPC9wPgo8cD7V4srH0ru49svjtbzJz7XEy7y/vMziMTUtMaGjPC9wPgo8cD7K18/Ivau4+LP2tcS148XF0PKjrLnYvPzX1nijrNbY0MKx4LrFo6y009fz1sHT0jGjrDKjrDOjrKGto6xuoaM8L3A+CjxwPrao0uVwW2ldW2pdo6yx7cq+veG142m1vb3hteNq1q685LXEvuDA66GjPC9wPgo8cD62qNLlZFtpXVtqXaOsse3KvrTTacGstb0xo6zU2bTTMcGstb1qo6yjqNei0uKjrGk+aqOsx9KyosO709DP4MGsoaOjqTwvcD4KPHA+PGltZyBzcmM9"http://www.2cto.com/uploadfile/Collfiles/20140323/20140323091259196.png" alt="\">

對於任意一個點i來說，有兩種連接方法，一種是如圖（a）所示，i與i-1相連，另一種呢是如圖（b），i與i-1不相連。

根據雙調旅程，我們知道結點n一定與n相連，那麼，如果我們求的d[n][n-1]，只需將其加上p[n-1][n]就是最短雙調閉合路線。

根據上圖，很容易寫出方程式：

dp[i][j]=dp[i-1][j]+dist[i][i-1];

dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dist[j][i]);

#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define min(a,b) ((a)<(b)?(a):(b))

const int N = 105;
int n, i, j;
double x[N], y[N], dp[N][N];

double dis(int v1, int v2) {
	return sqrt((x[v1] -  x[v2]) * (x[v1] -  x[v2]) + (y[v1] -  y[v2]) * (y[v1] -  y[v2]));
}

int main() {
	while (~scanf("%d", &n)) {
		double ans = INF;
		for (i = 1; i <= n; i++)
			scanf("%lf%lf", &x[i], &y[i]);
		dp[2][1] = dis(2, 1);
		for (i = 3; i <= n; i++) {
			dp[i][i - 1] = INF;
			for (j = 1; j < i - 1; j++) {
				dp[i][j] = dp[i - 1][j] + dis(i, i - 1);
				dp[i][i - 1] = min(dp[i][i - 1], dp[i - 1][j] + dis(j, i));
				if (i == n) ans = min(ans, dp[i][j] + dis(j, i));
			}
		}
		printf("%.2lf\n", min(ans, dp[n][n - 1] + dis(n - 1, n)));
	}
	return 0;
}