UVA 1347 Tour——dp

UVA 1347 Tour——dp

一开始以为是TSP，一看紫书n最大为1000，就直接断了这个念头，其实稍微一想就发现这个题固定了起点终点，所以不是TSP问题。

回到正题，这个题的特点是有两条线路，一条往一条反，完全可以看成两条从起点到终点的线路，我们设这两条线路为A B，定义dp【i】【j】为：A走到第i个点，B走到第j个点，且max（i，j）的点都被访问这个状态下的最下路程（很明显这个这样定义是没有后效性的），那么最终结果就是在dp【i:1~n-1】【n】+dis（i，n）中取最小值（注意dp【i】【j】=dp【j】【i】）。这样定以后很容易想到用刷表法更新，对于当前状态dp【i】【j】，max（i，j）已经完全被覆盖了，那么下一步应该更新max（i，j）+1这个位置，为了方便设t=max（i，j）+1，则

dp[t][j] = min(dp[t][j], dp[i][j]+dis(t, i));

dp[i][t] = min(dp[i][t], dp[i][j]+dis(t, j));

边界的话就是

dp[1][2] = dp[2][1] = dis(1, 2);

#include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1010;int n, x[maxn], y[maxn];double dp[maxn][maxn];double dis(int i, int j) { return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) scanf("%d %d", &x[i], &y[i]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = INF; } } dp[1][2] = dp[2][1] = dis(1, 2); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j || dp[i][j] > 1000000000) continue; int t = max(i, j)+1; dp[t][j] = min(dp[t][j], dp[i][j]+dis(t, i)); dp[i][t] = min(dp[i][t], dp[i][j]+dis(t, j)); } } double ans = INF; for (int i = 1; i < n; i++) ans = min(ans, dp[i][n]) + dis(i, n); printf("%.2lf\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。