DP+思维；模板类型
传送门：$>here<$
旅行商问题简化版。给出坐标系中n个点，要求从最左边出发，每一步只能往右走，走到最右边那个点。然后再从最右边那个点出发，每一步只能往左走，回到最左边那个点。整个过程中（除了起点），每个点仅能经过一次。问最短路？
数据范围：$n \leq 1000$
状压肯定不行。可以想到两张图，其中第二张图反向建边……但不能重复走这个问题很复杂……
从最右边往左走到最左边，前面提到了可以反向建边。那么除了发现建边，还可以将它看做是从左往右走的。于是问题转化为两个人从起点出发，走到最右边，两人不能经过同一个点。
题目告诉了我们x坐标各不相同。于是我们可以将所有点按照x坐标排序，于是就变成了一个一维的问题。有n个点排成一排，两两之间直接到达的路程已知。问两条路径共经过所有点的最短路。
容易发现由于所有点都要走到，那么一个人的路径确定以后另个人的路径一定确定。（就是去填补还没走的所有点）
起初想到了最朴素的DP，dp[i]表示两人走完前i个点，之后还要走的最短路。但发现这样的状态很难转移，因为不知道第二个人的具体位置。单单一个i不能描述一个状态。
于是我们增加一维j，表示1~i已经走完，且另一个人走到了j。（设i>j）。很容易发现j+1到i之间的所有点都是i走过的。这样的状态足以描述第一个人到i的时候所有的情况。
然后进行转移。是否需要向后全部扫描，枚举接下来走哪里？不需要。我们只需要考虑这个状态会做出的决策。由于只能单调向右走，那么i+1这个点一定需要走到。那么不是i走就是j走，不过两种决策。
i走到i+2不也是决策吗？
i要走到i+2，那么i+1必定是j走。换句话说，这种决策包含了j走到i+1.
尤其碰到这种题目让人搞不清楚的时候，问题转化很重要。想方设法弄清楚题目条件，在不改变条件的情况下转化为最简单的模式。
如果问题要求走过去再走过来往往是不太好考虑的。而我们熟悉的是两个人一起走过去，是可以等同的。这是一个套路。
这道题的复杂度之所以可以保证$O(n^2)$是因为决策只有两个。虽然一定要扫描k去转移也是可以的，但是这样的话就变n^3。考虑动态规划的决策时要考虑所有情况（全面），然后去除多余的情况（不包含）
有多种实现方法。最简单是记搜，此外填表法或刷表法都可以。其中记搜最好写，也最容易理解。（注意dp[n][i]的边界条件）
/*By DennyQi 2019*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int MAXN = 1010; const int MAXM = 20010; const int INF = 0x3f3f3f3f; inline int Max(const int a, const int b){ return (a > b) ? a : b; } inline int Min(const int a, const int b){ return (a < b) ? a : b; } inline int read(){ int x = 0; int w = 1; register char c = getchar(); for(; c ^ ‘-‘ && (c < ‘0‘ || c > ‘9‘); c = getchar()); if(c == ‘-‘) w = -1, c = getchar(); for(; c >= ‘0‘ && c <= ‘9‘; c = getchar()) x = (x<<3) + (x<<1) + c - ‘0‘; return x * w; } struct Coordinate{ double x,y; }a[MAXN]; int n; double dp[MAXN][MAXN]; bool vis[MAXN][MAXN]; inline bool cmp(const Coordinate& a, const Coordinate& b){ return a.x < b.x; } inline double dist(int i, int j){ double res = 0.0; res = sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y)); return res; } double DP(int a, int b){ if(a < b) swap(a,b); if(a == n){ return dist(b,n); } if(vis[a][b] || vis[b][a]) return dp[a][b]; vis[a][b] = vis[b][a] = 1; dp[a][b] = min(DP(a+1,b)+dist(a,a+1), DP(a,a+1)+dist(b,a+1)); dp[b][a] = dp[a][b]; return dp[a][b]; } int main(){ freopen(".in","r",stdin); n = read(); for(int i = 1; i <= n; ++i){ scanf("%lf%lf",&a[i].x,&a[i].y); } sort(a+1,a+n+1,cmp); printf("%.2f", DP(1,1)); return 0; }
dp[1][1] = 0; for(int i = 1; i <= n; ++i){ for(int j = i; j <= n; ++j){ if(i==j && i>1 && i<n) continue; if(j < n){ dp[i][j+1] = min(dp[i][j+1], dp[i][j] + dist(j,j+1)); dp[j][j+1] = min(dp[j][j+1], dp[i][j] + dist(i,j+1)); } else{ dp[n][n] = dp[i][n] + dist(i,n); } } }
dp[1][1] = 0; for(int i = 1; i <= n; ++i){ for(int j = i; j <= n; ++j){ if(i==j && i<n) continue; dp[i][j] = dp[i][j-1] + dist(j-1,j); if(i+1 == j){ for(int k = i-1; k >= 1; --k){ dp[i][j] = min(dp[i][j], dp[i][k] + dist(k,j)); } } dp[j][i] = dp[i][j]; } }
原文：https://www.cnblogs.com/qixingzhi/p/10372790.html