题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2224

题意:平面上有n个点,问去的路只能从左到右,回的路只能从右到左的,且来回必须经过所有点的最小路径;

dp[i][j] 表示以j为起点,1为拐点 ,i为终点的最短路;

j < i-1 时,那么i-1这个点在来的路径上 必然等于dp[i-1][j] + dis[i-1][i] ;

j = i -1 ,那么i-1这个点在回的路径上,那么dp[i][j] = min(dp[k][j] + dis[k][j]) 1<=k < j; 因为dp[i][j] = dp[j][i], 所以dp[i][j] = min(dp[j][k] + dis[k][j]) 1<=k < j

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <time.h>
#include <vector>
#include <queue> typedef long long LL; using namespace std; const int N = ;
const double eps = 1e-;
const int INF = 0x3f3f3f3f;
const int mod = ;
const double PI = *atan(1.0); struct point
{
double x, y;
}p[N]; double Dist(point p1, point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
} int n;
double dp[N][N];///表示以j为起点,1为拐点,i为终点,经历所有i到j之间的点;
/*
double DP()
{
dp[1][1] = 0;
dp[2][1] = Dist(p[1], p[2]);
for(int i=3; i<=n; i++)
{
for(int j=1; j<i-1; j++)
dp[i][j] = dp[i-1][j] + Dist(p[i-1],p[i]);
double Min = INF;
for(int k=1; k<i-1; k++)
Min = min(Min, dp[i-1][k] + Dist(p[k], p[i]));
dp[i][i-1] = Min;
}
dp[n][n] = dp[n][n-1] + Dist(p[n-1], p[n]);
return dp[n][n];
}*/ double DFS(int s, int e)
{
if(dp[s][e] != )
return dp[s][e];
if(s < e-)
dp[s][e] = DFS(s, e-) + Dist(p[e-], p[e]);
else
{
double Min = INF;
for(int i=; i<e-; i++)
Min = min(Min, DFS(i, s) + Dist(p[i], p[e]));
dp[s][e] = Min;
}
return dp[s][e];
} int main()
{
while(scanf("%d", &n) != EOF)
{
memset(dp, , sizeof(dp));
for(int i=; i<=n; i++)
scanf("%lf %lf", &p[i].x, &p[i].y);
///double ans = DP();
dp[][] = ;
dp[][] = dp[][] = Dist(p[], p[]);
DFS(n-, n);
dp[n][n] = dp[n-][n] + Dist(p[n-], p[n]);
printf("%.2f\n", dp[n][n]);
}
return ;
}

最新文章

  1. Flask备注二(Configurations, Signals)
  2. Eclipse问题集锦
  3. NSString格式校验
  4. Java中使用Jedis操作Redis
  5. WPF循环加载图片导致内存溢出的解决办法
  6. codeforces 487B B. Strip(RMQ+二分+dp)
  7. scala模拟一个timer
  8. 一,U盘安装 CentOS 6.5 minimal
  9. Dom文档模型
  10. java.lang.ClassFormatError: Illegal UTF8 string in constant pool in class file Server/Request
  11. 大区间素数筛选 POJ2689
  12. Buy the Ticket HDU 1133 递推+大数
  13. DLL模块:extern &quot;C&quot;的简单解析
  14. c语言memset详解
  15. vue 动态变量值不变化
  16. centos7/rhel7下安装redis4.0集群
  17. SVN常用命令说明
  18. [UE4]Wrap Box流布局
  19. C# 枚举基本用法及扩展方法
  20. BZOJ3175[Tjoi2013]攻击装置——二分图最大独立集

热门文章

  1. 【笔记】cookies管理工具类
  2. xcode 常见错误报错问题!
  3. 开放封闭原则(Open Closed Principle)
  4. CSS基础及选择器
  5. C++ 的二进制语法与语义
  6. jquery实现页面交互的几个小例子
  7. ExtJS 中自定义类
  8. 打造自己的php动态连接库文件
  9. BestCoder Round #86
  10. Apache rewrite