前言

这道题的思路十分巧啊~

题目

传送门:
Vjudge
UVa(有点慢)

题目大意:
在平面上给你n(n<=1000)个点的坐标(按照x递增给出,各x坐标不同,且均为整数),现在你要设计一条路线,从最左边出发,走到最右边的点后再返回,要求除了最左点和最右点之外每个点恰好经过一次,且路径总长最短.两点间距离为欧几里德距离。
$in$

3
1 1
2 3
3 1
4
1 1
2 3
3 1
4 2

$out$

6.47
7.89

思路

在这里我们其实发现连成一个环并且计算距离是比较困难的,所以我们可以换一种思路:
如下图,

我们现在随便找一个环:

我们其实可以把$1->n->1$这个环看成是由两段线段组成的:也就是$1->n+1->n$

那么问题就改成:两个人都从最左点出发,沿两条除起点和终点相同,其余点均不同的路径恰好所有点均被访问过得路径和的最小值。
我们定义:
$f[i][j]:从起点开始,此时一个人走到i，另一个人走到j的路径和的最小值$
注意,此时两个人的路径最多只有两个点是重合的.
我们其实发现,这样的状态比较难进行转移,而且还有重复,就像f[i][j]其实是等于f[j][i]的,那我们就强行规定i>j,这样的话不管下一次转移是哪一个人进行转移,就只能走到$i+1,i+2,...,n$这些点,可是如果我们直接走到了i+2,我们就不能保证i+1是否被走过,那我们就可以直接每次只走i+1也就是下一个点,这样我们就可以保证当前1~i必然都已访问完。
下图就是在更行i=4的情况:


我们可以发现,对于i这个点来说,我们要么是在所有j中选取一个最优的j跳过来,要么是由i-1直接走一步，因为这样我们才能保证$1~i$全部访问过。然后如果j>i了的话我们就把j提前写在第一维,i写在第二维.

状态转移方程

我们的状态转移方程就是:
①我们j从j这个点直接跳到i，而i-1这个点没有动,由于跳转后j>i，j提前：
$f[i][i-1]=min{f[i-1][j]+dis[i][j]|i<=n\quad j<i}$
①的状态转移方程原本是:
$f[i-1][i]=min{f[i-1][j]+dis[i][j]|i<=n\quad j<i}$
当然,这样写是不对的.

②由i-1跳到i，而j这个点没有动
$f[i][j]=f[i-1][j]+dis[i-1][i](i<=n\quad j<i)$
注意这里的dis是预处理出来的

统计答案

最后统计答案的时候不是直接统计$f[n][n]$(我一开始这样错了),因为i，j两点是永远不可能在一起的(hhh~)，最后结束的地方需要我们自己来操作,我们就直接统计
$min{f[n][i]+dis[i][n]}(1<=i<n)$的答案就可以了

有关初值

由于i,j不重合,直接令$f[2][1]=dis[1][2]$就可以了

代码

#include<cmath>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
int read(){int f=1,x=0;char s=getchar();while(s<'0'||s>'9'){
   if(s=='-')f=-1;s=getchar();}  while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}return x*f;
}
#define MAXN 1000
#define INF 0x3f3f3f3f
struct node{
   //定义结构体保存点的信息int x,y;node(){}node(int X,int Y){x=X,y=Y;}
}dot[MAXN+5];
double f[MAXN+5][MAXN+5];//f[i][j]:1~i全部走过
double dis[MAXN+5][MAXN+5];//一个人在i,另一人在j的距离和最小值
int main(){int n;while(~scanf("%d",&n)){for(int i=1;i<=n;i++){int x=read(),y=read();dot[i]=node(x,y);}for(int i=1;i<=n;i++)//预处理for(int j=1;j<=n;j++)dis[i][j]=dis[j][i]=sqrt(1.0*(dot[i].x-dot[j].x)*(dot[i].x-dot[j].x)+1.0*(dot[i].y-dot[j].y)*(dot[i].y-dot[j].y));f[2][1]=dis[1][2];//初始化for(int i=3;i<=n;i++){f[i][i-1]=INF*1.0;//注意是取min所以初值为INFfor(int j=1;j<i-1;j++){f[i][i-1]=min(f[i][i-1],f[i-1][j]+dis[i][j]);f[i][j]=f[i-1][j]+dis[i][i-1];}}double ans=INF;//统计答案for(int i=1;i<n;i++)ans=min(ans,f[n][i]+dis[i][n]);printf("%.2lf\n",ans);}return 0;
}

题外话

这种做法我觉得是我肯定要想很久很久,$O(n^2)$的做法极为朴实易懂,再次膜拜刘汝佳~