题目大意：给出n个点，要求你从最左边那个点走到最右边那个点，每个点都要被遍历过，，且每个点只能走一次，问形成的最短距离是多少
解题思路：用dp[i][j]表示第一个人走到了第i个点，第二个人走到了第j个点且已经遍历了1–max(i,j)的所有点的最短距离。因为dp[i][j] = dp[j][i]的，所以我们设i > j的 那么就有 当j < i-1 时，dp[i][j] = dp[i-1][j] + dis(i, i -1) 当j == i + 1时情况就比较特别了,这里将j用i－1代替 dp[i][i – 1] = min(dp[i][i-1], dp[i-1][k] + dis(k,j)) 具体的证明可以去百度查找：双调欧几里得旅行商问题 还有另一种写法我还是不懂
;const int N = 1010;const double INF = 0x3f3f3f3f3f3f3f3f;double dp[N][N], dis[N][N];int n;struct point{double x, y;}P[N];double distance(int a, int b) {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));}void init() {for(int i = 1; i <= n; i++)scanf(“%lf%lf”, &P[i].x, &P[i].y);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)dis[i][j] = dis[j][i] = distance(i,j);}double solve() {dp[2][1] = dis[2][1];for(int i = 3; i <= n; i++) {dp[i][i-1] = INF;for(int j = 1; j < i – 1; j++) {dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis[j][i]);dp[i][j] = dp[i-1][j] + dis[i][i-1];}}double ans = INF;for(int i = 1; i < n; i++)ans = min(ans, dp[n][i] + dis[i][n]);return ans;}int main() {while(scanf(“%d”, &n) != EOF && n) {init();printf(“%.2lf\n”, solve());}return 0;}
你可能付出一定的代价，但日后你得到的，远比付出的多得多。
