链接：1347 - Tour
没想通，看了题解，学习了。。。
思路【转】： 欧几里得旅行商问题是对平面上给定的n个点确定一条连接各点的最短闭合旅程的问题。如图（a）给出了一个7个点问题的解。这个问题的一般形式是NP完全的，故其解需要多于多项式的时间。J.L. Bentley 建议通过只考虑双调旅程(bitonic tour)来简化问题,这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。下图(b)显示了同样的7个点的最短双调路线。在这种情况下，多项式的算法是可能的。事实上，存在确定的最优双调路线的O(n*n)时间的算法。
图a 
图b< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+16I61NrSu7j2taXOu9WkJiMyNjY4NDvJz8/Uyr61xMa9w+bJz7XExt+49rXjoaMgYSnX7rbMsdW6z8K3z98ss6S2yLTz1LzKxzI0Ljg5oaPV4rj2wrfP37K7ysfLq7X3tcSho2Ipz+DNrLXjtcS8r7rPyc+1xNfutszLq7X3sdW6z8K3z9+ho7Oktsi089S8yscyNS41OKGjPC9wPgo8cD7V4srH0ru49svjtbzJz7XEy7y/vMziMTUtMaGjPC9wPgo8cD7K18/Ivau4+LP2tcS148XF0PKjrLnYvPzX1nijrNbY0MKx4LrFo6y009fz1sHT0jGjrDKjrDOjrKGto6xuoaM8L3A+CjxwPrao0uVwW2ldW2pdo6yx7cq+veG142m1vb3hteNq1q685LXEvuDA66GjPC9wPgo8cD62qNLlZFtpXVtqXaOsse3KvrTTacGstb0xo6zU2bTTMcGstb1qo6yjqNei0uKjrGk+aqOsx9KyosO709DP4MGsoaOjqTwvcD4KPHA+PGltZyBzcmM9"https://www.cppentry.com/upload_files/article/49/1_lxuef__.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; }