题解 P1523 【旅行商简化版】

· · 题解

这是一道DP题

思路

题目要求一条最短的哈密顿回路，即每个点只能经过一次

首先我们可以根据样例画出图来

如图是一个哈密顿回路，我们可以将其看成有两个人一起从最左边的点出发，走不同的路，一起到最右点，两人途中将每个点都刚好经过一次

在开始前先将所有点按x坐标sort一遍，方便做题

于是可以设状态d(x,y)表示两个人已经经过了1~max(x,y)的所有点，且此时一个人在x点，另一个人在y点，两个人距终点的最短距离。

易得d(x,y)=d(y,x)，所以可以设x>y，但是如果一个人往x+2走，中间会少x+1这个点没被走过，无法表示成状态。

但是我们还有一个方法：限制这两人只能走x+1这个点

这样做是否正确呢？

其实可以证明，即使有一个人向x+2这个点走，为了使1~x+2都被走过，也要让另一个人去走x+1这个点，所以不必担心漏掉最优解

接下来上状态转移方程（使用dis(x,y)代表x点与y点间的欧几里得距离）

d(x,y)=min( d(x+1,y)+dis(x,x+1), d(x,x+1)+dis(y,x+1) )

其实也就是代表两个人分别走到x+1点的两种状态,使用的是逆推法

边界为d(n-1, j)=dis(n-1,n)+dis(j,n)，其中0<j<n-1

最终答案为dis(1,2)+d(2,1)

这里不再证明，读者应当可以通过定义自己推出

思路就讲到这里，更详细的就请见代码吧

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
double d[1001][1001];
struct node{//记录每个点 
    double x,y;
}a[1010];
bool cmp(node a,node b)
{
    return a.x<b.x;
}
double dis(double x1,double y1,double x2,double y2)//距离公式 
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
    scanf("%d",&n); 
    memset(d,0,sizeof(d));
    for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);//排序 
    double dis1=dis(a[n].x,a[n].y,a[n-1].x,a[n-1].y),dis2=dis(a[1].x,a[1].y,a[2].x,a[2].y);
    for(int i=1;i<n-1;i++)d[n-1][i]=dis(a[n].x,a[n].y,a[i].x,a[i].y)+dis1;//初始化边界 
    for(int i=n-2;i>=2;i--)//逆推 
    {
        for(int j=1;j<i;j++)
        {
            d[i][j]=d[i+1][j]+dis(a[i].x,a[i].y,a[i+1].x,a[i+1].y);
            d[i][j]=min(d[i][j],d[i+1][i]+dis(a[j].x,a[j].y,a[i+1].x,a[i+1].y));
        }
    }
    printf("%.2lf\n",dis2+d[2][1]);//计算答案 
    return 0;
}

求管理员大大通过