https://cn.vjudge.net/problem/UVA-1347
题目
给定平面上 $n$($nleqslant 1000$)个点的坐标(按照 $x$ 递增的顺序给出。各点 $x$ 坐标不同,且均为正整数),你的任务是设计一条路线,从最左边的点除法,走到最右边的点后再返回,要求除了最左点和最右点之外每个点恰好经过一次,且路径总长度最短。两点间的长度为他们的欧几里得距离。
题解
可以通过一种状态的设法使所有状态组成DAG。
因为结果有多个,如果使用递推,那么设当前节点到末尾还需要走多长,这样可以避免最后循环求一次最少(实际是为了方便打印字典序最小的解)
头晕,可能不对,以后好了再想……(虽然是水题,但是还是理不清楚)
AC代码
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #include<bits/stdc++.h> using namespace std; #define REP(r,x,y) for(register int r=(x); r<(y); r++) #define PER(r,x,y) for(register int r=(x); r>(y); r--) #define REPE(r,x,y) for(register int r=(x); r<=(y); r++) #define PERE(r,x,y) for(register int r=(x); r>=(y); r--) #ifdef sahdsg #define DBG(...) printf(__VA_ARGS__) #else #define DBG(...) (void)0 #endif #define MAXN 1007 struct p { int x,y; inline bool operator<(p&rhs) const { return x<rhs.x; } } arr[MAXN]; double dp[MAXN][MAXN]; double dis[MAXN][MAXN]; inline double getdis(int i, int j) { double dx=arr[i].x-arr[j].x; double dy=arr[i].y-arr[j].y; return sqrt(dx*dx+dy*dy); } int main() { #ifdef sahdsg freopen("in.txt", "r", stdin); #endif int n; while(~scanf("%d", &n)) { memset(dis,0,sizeof dis); REP(i,0,n) { scanf("%d%d", &arr[i].x, &arr[i].y); } sort(arr,arr+n); REP(i,1,n) { REP(j,0,i) { if(i==j) continue; dis[i][j]=dis[j][i]=getdis(i,j); } } REP(i,0,n) { dp[n-2][i]=dis[n-2][n-1] + dis[i][n-1]; } PERE(i,n-3,0) { REPE(j,0,i) { dp[i][j] = min(dp[i+1][i]+dis[j][i+1], dp[i+1][j]+dis[i][i+1]); } } printf("%.2lf ", dp[1][0]+dis[0][1]); } return 0; }