本文共 1776 字，大约阅读时间需要 5 分钟。

目录

时间限制: 1 Sec  内存限制: 64 MB

题目描述

xiaomengxian一进门，发现外公、外婆、叔叔、阿姨……都坐在客厅里等着他呢。经过仔细观察，xiaomengxian发现他们所有人正好组成了一个凸多边形。最重要的是，他们每个人手里都拿着一个红包（^o^）。于是非常心急，xiaomengxian决定找一条最短的路线，拿到所有的红包。 假设屋里共有N个人拿着红包，把他们分别从1到N编号。其中，编号为1的人就坐在大门口，xiaomengxian去拿红包。一条合法的路线必须经过所有的点一次且仅一次。

输入

第一行为一个整数N（1<=N<=800）。 以下N行，每行两个实数Xi，Yi，表示该点的坐标。 各个点按照逆时针顺序依次给出。

输出

一个实数，表示最短的路线长度（保留三位小数）。

思路

此题在数据 / OJ 差的情况下，是可以用鬼贪心卡过的。但是这毕竟不是正解，正如标题上说的，要用动态规划求解，还要用“四边形不等式”来优化DP，其实，要是不用四边形不等式，还想不出是DP方法呢。

首先，

题目中说了，所有人正好组成了一个凸多边形，所以，题目是在提示我们，要用到凸多边形的性质。就拿四边形举例吧。

我们会发现，它的边长是符合四边形不等式的！

                                                                                            即 AD + BC > AB + CD 

我们若从任意一点（A）出发，要最终走出一条最短路的话，先走对角线（AD）是不可取的，因为根据路径的特点，这样最终总会走过另一条不优的对角线（BC），与其如此，还不如先走一条与之相连的边（AB），最终的路径才可能是最优的 。 

可以根据三角形三边关系去证明。

同理，

再看一个多边形。

从一个顶点A出发，若是走对角线，那么下一步只能走C或D，那么最后总会连一条不优的对角线交叉。

也就是说，在一个多边形的一点开始，第一步只能走相邻点。

整条路就可以用DP来解决。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define min(x,y) (x < y ? x : y)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;}int n,m,i,j,k,s,o,t;double x[805],y[805],dp[805][805][2],ans;double HF(int a,int b) { return sqrt(pow(x[a] - x[b],2) + pow(y[a] - y[b],2));}double DP(int l,int r,int f) { if(dp[l][r][f] > 0.0) return dp[l][r][f]; if(l == r) return 0.0; int u = l + 1,v = l - 1; if(u > n) u = 1; if(v < 1) v = n; if(f) dp[l][r][f] = min(HF(l,u) + DP(u,r,1),HF(l,r) + DP(r,u,0)); else dp[l][r][f] = min(HF(l,v) + DP(v,r,0),HF(l,r) + DP(r,v,1)); return dp[l][r][f];}int main() { n = read(); for(i = 1;i <= n;i ++) { scanf("%lf%lf",&x[i],&y[i]); } ans = DP(1,n,1); for(i = 2;i <= n;i ++) { ans = min(ans,DP(i,i - 1,1)); } printf("%.3lf",ans); return 0;}
        
       
      
     
    
   

转载地址：https://blog.csdn.net/weixin_43960414/article/details/86476181 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！