URAL 1143 Electric Path

URAL 1143 Electric Path

( ​​ Background At the team competition of the 10th national student informatics Olympic, which is organized at Hanoi National University, there are N teams participating. Each team is assigned to work in a camp. On the map, it can be seen that the camps are positioned on the vertices of a convex polygon with N vertices: P1, P2, …, PN (the vertices are enumerated around the polygon in counter-clockwise order.) In order to achieve absolute safety providing electricity to the camps, besides an electric supplying system, the host organization set up a path from a reserved electricity generator (which is placed in one of the camps) to every camp once, and the path’s total length is minimum. Problem Given the coordinates of the polygons’ vertices (the camps’ positions), determine the length of the electric path corresponding to the host organization’s arrangement. Input The first line contains the integer N (1 ≤ N ≤ 200). The i’th line of the next N lines contains two real numbers xi, yi, separated by a space, with no more than 3 digits after the decimal points, are vertex Pi’s coordinates on the plane (with i = 1, 2, …, N). The length of the path connecting two vertex (xi, yi) and (xj, yj) is computed with the formula: sqrt((xi − xj)2 + (yi − yj)2). Output The only line should contain real number L (written in real number format, with 3 digits after the decimal point), which is the total length of the electric path. Sample input output

4 50.0 1.0 5.0 1.0 0.0 0.0 45.0 0.0

50.211

强啊 还是icefox最强啦qwq %%%这些dp题我哪会啊 题意：求一个凸包上哈密尔顿距离最小是多少 那么不是所有边都连是最好的 比如 四个点 我可以连成z字形状 且因为这是凸包上的最短哈密顿路径 所以一定不能相交 那么就可以考虑dp来解决了 如何搞？ 设dp[i][l][0/1]表示 我当前正好要做的区间是i~i+l-1 求问这一段的哈密顿距离最小是多少 那么显然我这个dp方程有两种转移 有可能我是i+1~i+l-1—->i~i+l-1 或者是i~i+l-2—->i~i+l-1 然后分类讨论一下即可 dp[0][i][len]=min(dp[0][i+1][len−1]+dis[i][i+1],dp[1][i+1][len−1]+dis[i][i+len−1]); dp[1][i][len]=min(dp[1][i][len−1]+dis[i+len−1][i+len−2],dp[0][i][len−1]+dis[i][i+len−1]); 答案为min{dp[0][i][n]|1≤i≤n}复杂度是O(n2)的

#include#include#include#define N 220using namespace std; double x[N],y[N],dp[N][N][2],dis[N][N];int n;//dp表示从i开始长度为len的最短哈密尔顿距离是多少 //0表示在左端 1表示在右端 int main(){ freopen("ural1143.in","r",stdin); scanf("%d",&n); for (int i=0;i

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