点击打开链接
题意:给出n个点坐标 要求从起到走到终点在走回起点的总路程最小&&中间点要恰好经过一次 n<=1e3
从起点到终点在走回起点,可以看成两个人同时从起点到终点&&路径不相交的最短走法
设dp[i][j]为两个人分别在第i,j点时候&&前max(i,j)点恰好都经过一次,此时最少需要多少距离才能到终点 人可以互换 所以dp[i][j]=dp[j][i] 则默认i>j,则第i+1个点只有两种可能要么第一个人走到要么第二个人走到
dp[i][j]=min(dp[i+1][j]+dist(i,i+1),dp[i+1][i]+dist(j,i+1)) (dist[i][i+1]==dist[i+1][i])
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N=2e3+20; pair<double,double> p[N]; int n; double dp[N][N]; double dist(int i, int j) { double dx = p[i].first - p[j].first; double dy = p[i].second - p[j].second; return sqrt(dx*dx+dy*dy); } int main() { while(cin>>n) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) dp[i][j]=1e8; } for(int i=1;i<=n;i++) cin>>p[i].first>>p[i].second; for(int j=1;j<n-1;j++) dp[n-1][j]=dist(n-1,n)+dist(j,n); for(int i=n-2;i>=1;i--) { for(int j=1;j<i;j++) { dp[i][j]=min(dp[i+1][j]+dist(i,i+1),dp[i+1][i]+dist(j,i+1)); } } printf("%.2lf\n",dp[2][1]+dist(1,2)); } return 0; }