学习笔记 P1523 旅行商简化版
题目背景
欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解，但是有办法在多项式时间内求出一个较优解。
为了简化问题，而且保证能在多项式时间内求出最优解，J.L.Bentley提出了一种叫做bitonic tour的哈密尔顿环游。它的要求是任意两点(a,b)之间的相互到达的代价dist(a,b)=dist(b,a)且任意两点之间可以相互到达，并且环游的路线只能是从最西端单向到最东端，再单项返回最西端，并且是一个哈密尔顿回路。
题目描述 著名的NPC难题的简化版本
现在笛卡尔平面上有n(n<=1000)个点，每个点的坐标为(x,y)(-2^31<x,y<2^31，且为整数)，任意两点之间相互到达的代价为这两点的欧几里德距离，现要你编程求出最短bitonic tour。
输入格式：
第一行一个整数n
接下来n行，每行两个整数x,y，表示某个点的坐标。
输入中保证没有重复的两点，
保证最西端和最东端都只有一个点。
输出格式：
一行，即最短回路的长度，保留2位小数
题意分析
由于此题存在简化
实现从左到右 再从右到左 所以直接简单DP
首先预处理出任意两点之间的欧几里得距离
同时顺道初始化dp数组
然后我们使用dp[i][j]
表示第一个人到达i 第二个人到达j的最小代价(i<j)
然后为了防止重复行走
接下来TA们中的一个人将走到(j+1)
1.在j的那一个人到达(j+1) 状态变更为dp[i][j+1]
也就是min{dp[i][j]+dis[j][j+1]}
2.在i的那一个人到达(j+1) 状态变更为dp[j][j+1]
也就是min{dp[i][j]+dis[i][j+1]}这样之后 就可以DP了
由于最后不确定是停在那里了
所以ans=min{dp[i][n]+dis[i][n]}
CODE:
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define int long long
#define inf 1e30
#define N 500008
#define IL inline
#define M 1008611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>void read(T &a)
{
T x=0,f=1;char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')f=0;ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
}
a=f?x:-x;
}
/*-------------OI使我快乐-------------*/
struct Node{
D xi,yi;
}e[1010];
D dp[1010][1010];
D dis[1010][1010];
IL D dmin(D a,D b) {return a<b? a:b;}
IL D youngsc(int x,int y)
{
return sqrt((e[x].xi-e[y].xi)*(e[x].xi-e[y].xi)+(e[x].yi-e[y].yi)*(e[x].yi-e[y].yi));
}
int n;
IL bool cmp(Node A,Node B)
{return A.xi<B.xi;}
signed main()
{
read(n);
for(R int i=0;i<n;++i)
{
scanf("%lf%lf",&e[i].xi,&e[i].yi);
}
sort(e,e+n,cmp);
for(R int i=0;i<n;++i)
for(R int j=i+1;j<n;++j)
{
dis[i][j]=youngsc(i,j);
// cout<<i<<" "<<j<<" "<<dis[i][j]<<endl;
dp[i][j]=inf;
}
dp[0][1]=dis[0][1];
for(R int i=0;i<n;++i)
for(R int j=i+1;j<n;++j)
{
dp[i][j+1]=dmin(dp[i][j+1],dp[i][j]+dis[j][j+1]);
dp[j][j+1]=dmin(dp[j][j+1],dp[i][j]+dis[i][j+1]);
}
D ans=inf;
for(R int i=0;i<n-1;++i) ans=dmin(ans,dp[i][n-1]+dis[i][n-1]);
printf("%.2lf\n",ans);
return 0;
}