uva 1347 旅行 动态规划

题目链接戳这里
太菜了..觉得这题好难...
大意是有n个按x坐标递增顺序给出的一些点，如何从最左点走到最右点，再从最右点走到最左点，路径总长度最短。要求除最左和最右外每个点恰好经过一次。

紫书的思路我这整理一下:
“从左到右再回来”思考不方便，改成：2人同时从最左出发，沿不同的路径走，最后都走到最右点，且除起点和终点外每个点恰好被1人经过。用d(i,j)表示第1个人走到i，第2个人走到j，还需走多长的距离。

但是这样很难保证2人不会走相同的点。比如计算状态d(i,j)，能不能让i走到i+1呢？不确定。说明这种状态定义不好。改用d(i,j)表示从1到max(i,j)的点都走过了，现在的位置是i和j，还需要走多长距离。

• 可以发现d(i,j)=d(j,i)，可以规定i>j。①

那么下一步可以走的点有i+1,i+2...如果走了i+2，情况是走过了1~i和i+2，i+1没走过，无法用d来表示状态，于是规定下一步不管是谁，总是走i+1.这里有个关键的地方：上述规定不会导致漏解，因为第1人若是直接走到i+2，再也无法走到i+1，只能靠第2人走到i+1。反正第2人都要走到i+1，不如当前就直接让第2人走到i+1的情况来看看。

• 所以，现在的情况就是：对于d(i,j) 下一步只有两种转移决策，要么是i走到i+1，要么是j走到 i+1;

d(i,j)只能转移到d(i＋1,j)和d(i＋1,i)， 第1个d代表第1人从i走到i+1，第2个d表示j走到i+1，即d(i,i+1)，但是由于①处的规定，因d(i,i+1)=d(i+1,i)，写作d(i+1,i)

到这儿，麻烦的就是边界条件了：d(n-1,j)=dist(n-1,n)+dist(j,n)，其中dist(a,b)表示点a和点b的距离。即只剩最后一个点(编号n)没走了，那么还剩多少路要走？2人到最后个点的距离之和便是了。

解是什么?

是dist(1,2)+d(2,1)，那为什么不写d(1,1)算了?别忘了规定①要求i>j喔.所以往前推一步。第一步定是有人到第二点，解为dist(1,2) 加从这种情况开始的所需距离..
代码:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
const int inf = 0x3f3f3f3f, maxN = 50 + 5;
int N, M;
double x[maxN], y[maxN], dist[maxN][maxN], d[maxN][maxN];

int main() {
    // freopen("data.in", "r", stdin);
    while (~scanf("%d", &N)) {
        rep(i, 1, N + 1)
            scanf("%lf %lf", &x[i], &y[i]);
        rep(i, 1, N + 1)
            rep(j, 1, N + 1)
                dist[i][j] = sqrt(pow((x[i] - x[j]), 2)
                        + pow((y[i] - y[j]), 2));
        rrep(i, 2, N) {
            rep(j, 1, i) {
                if (i == N - 1)
                    d[i][j] = dist[i][N] + dist[j][N];
                else
                    d[i][j] = min(dist[i][i + 1] + d[i + 1][j],
                            dist[j][i + 1] + d[i + 1][i]);
            }
        }
        printf("%.2lf\n", dist[1][2] + d[2][1]);
    }
    return 0;
}

这里放张网友的心声..扎铁