ACM - 动态规划 - UVA 1347 Tour
题解
题目大意:有 \(n\) 个点,给出点的 \(x\)、\(y\) 坐标。找出一条经过所有点一次的回路,从最左边的点出发,严格向右走,到达最右点再严格向左,回到最左点。问最短路径距离是多少?
这题原始的问法是不加严格向左严格向右的边界条件,也即著名的旅行商问题(TSP 问题),原问题已经被证明是一个 NP 难的问题。但在此题的限制条件下,我们可以在多项式时间里解决该问题。
我们可以试着从最左边往右走,当准备经过一个点时,它只有两种可能,一是从左往右时经过该点,二是从右往左经过该点。我们可以直接将问题等价为:两个人都从最左边往最右边行走(\(x\) 坐标严格大),每个点都被经过且仅被一个人经过(除起点和终点,起点和终点被各自经过一次),使两条路径加和最短。
显然同一个 \(x\) 坐标的点的数量最多两个,如果有至少三个点会使得至少一个点不能被这两人经过(路径要求 \(x\) 坐标严格大),此时必定不能形成回路。
我们使用动态规划求解,令 \(dp[i][j]\) 表示点 \(1 \sim max(i,j)\) 全部走过,且两个人的当前位置分别是点 \(i\) 和 \(j\),还需要走多长的距离到达最右边(终点)。
状态转移方程
考虑状态 \(dp[i][j]\),由于此时点 \(1 \sim max(i,j)\) 全部走过,因此要达到此状态,只有两种可能,点 \(max(i,j)+1\) 由第一个人走,点 \(max(i,j)+1\) 由第二个人走。
用 \(dist(m_1, m_2)\) 函数表示点 \(m_1\) 到 点 \(m_2\) 的欧几里得距离。此时若 \(i > j\),
第一种情况表示为
\]
第二种情况表示为
\]
综上,写出状态转移方程:
\]
我们再考虑边界的状态,边界如下
\]
状态搜索方向
使用递归做状态搜索,此方法的另一种名称叫记忆化搜索,但我个人倾向于将记忆化搜索视为动态规划的递归实现(即使用递归用状态搜索)。
程序实现
使用 C++ 实现算法。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define PII pair<int, int>
#define INF 0x3f3f3f3f
using namespace std;
struct point
{
double x; // x 坐标
double y; // y 坐标
}ps[1005];
double dp[1005][1005];
double dist(int i, int j)
{
return sqrt((ps[i].x - ps[j].x) * (ps[i].x - ps[j].x) +
(ps[i].y - ps[j].y) * (ps[i].y - ps[j].y));
}
double fun(int i, int j)
{
if (dp[i][j] > 0)
return dp[i][j];
return dp[i][j] = min(fun(i + 1, j) + dist(i, i + 1),
fun(i + 1, i) + dist(j, i + 1));
}
int main()
{
int N = 1;
while (cin >> N) {
for (int i = 1; i <= N; ++i)
cin >> ps[i].x >> ps[i].y;
memset(dp, 0, sizeof(dp));
for (int j = 1; j < N - 1; j++)
dp[N - 1][j] = dist(N - 1, N) + dist(j, N);
double ans = fun(1, 1);
printf("%.2f\n", ans);
}
return 0;
}
最新文章
- 全球PM25实时可视化
- Allocators与Criterion的相同点及区别
- 在centos 7.0上利用yum一键安装mono
- SSH整合(struts2.3.24+hibernate3.6.10+spring4.3.2+mysql5.5+myeclipse8.5+tomcat6+jdk1.6)
- 使用集成的ADT bundle来搭建android开发环境
- [html]选项卡效果
- STM8s窗口看门狗
- ASP.NET-FineUI开发实践-6
- android代码控制seekbar的样式
- PHP学习之-面向对象
- 基于飞思卡尔i.MX 6Quad Sabrelite开发板的触摸屏调试
- STM32按键控制程序
- sql语句可以截取指定字段后面的字符串
- 在HTML中限制input 输入框只能输入纯数字
- Object 转 json 工具类
- 记录一次向TiDB数据库导入数据的例子
- 阿里云url解析,发布web后去除url中的端口号
- MySQL递归查询树状表的子节点、父节点
- MyEclipse中jquery.js文件报missing semicolon的错误解决
- iOS调试证书/公布证书制作