& & 题目链接:hdu 4824 Disk Schedule& & 题目大意：中文题。& & 解题思路：需要的时，很明显每到一层是要读取一次数据的，但是因为需要返回00,所以有些层的数据可以在返回的过程中读取会较优。于是转化成了双调欧几里得旅行商问题。&code class="hljs cpp"&#include&cstdio&#include&cstring&#include&cstdlib&#includeconst int N = 1005;const int INF = 0x3f3f3f3f;int n, p, d[N], dp[N][N];int dis (int a, int b) {
int tmp = abs(d[a] - d[b]);
return min(tmp, 360 - tmp);}void init () {
scanf("%d", &n);
for (int i = 2; i&= n + 1; i++) {
scanf("%d%d", &a, &d[i]);
if (i == n + 1)
dp[2][1] = dis(1, 2);}int solve () {
for (int i = 3; i&= n + 1; i++) {
dp[i][i-1] = INF;
for (int j = 1; j& i-1; j++) {
dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis(i, j));
dp[i][j] = dp[i-1][j] + dis(i, i-1);
int ans = INF;
for (int i = 1; i&= i++)
ans = min(ans, dp[n+1][i] + dis(n+1, i));}int main () {
scanf("%d", &cas);
for (int i = 1; i&= i++) {
printf("%d\n", solve() + p * 800 + 10 * n);
return 0;}&/code&
声明：该文章系网友上传分享，此内容仅代表网友个人经验或观点，不代表本网站立场和观点；若未进行原创声明，则表明该文章系转载自互联网；若该文章内容涉嫌侵权，请及时向
上一篇：下一篇：
相关经验教程
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.002 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
论文写作技巧双调欧几里得旅行商问题
双调欧几里得旅行商问题
问题的描述如下(书中231页)：
平面上n个点，确定一条连接各点的最短闭合旅程。这个解的一般形式为NP的（在多项式时间内可以求出）。
J.L. Bentley 建议通过只考虑双调旅程(bitonic tours)来简化问题,这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。下图(b)显示了同样的7个点的最短双调路线。在这种情况下，多项式的算法是可能的。事实上，存在确定的最优双调路线的O(n*n)时间的算法。
& & & & & & & & & & & &（a） & & & & & & & & & & & & & & & (b)
（a）图是最短的闭合旅程，长度为24.89。（b）图是问题经简化后，同样的点集的最短双调闭合旅程，长度为25.58。
解题思路：
根据简化后的双调欧几里得旅行问题的性质，将点集依据各点x坐标单调递增来进行编号，我们设b[i,j]是最短双调闭合旅程P(i,j)的长度(i&=j)，而最短双条闭合旅程P(i,j)是指从点P[i]开始,严格地向左走（即是每次经过的点的x坐标都比前一个点的x坐标要小），直到最左点P[1],然后再严格向右走，直到终点P[j]为止，在从P[i]到P[j]过程中的点有且只经过一次。设distance[i,j]是点P[i]到P[j]之间的欧式距离。
那么，根据动态规划的方法，我们要找出问题的最优子结构，并且递归定义出来，下面是问题的公式（大前提是i&=j）：
b[1,2]=distance(1,2)；最小的子问题，主要用于求解更大的子问题；
b[i,j]=b[i,j-1] + distance(j-1,j),如果i
b[i,j]=min{ b[k,j-1] + distance(k,j) }，其中1&=k
下面讲解公式的由来，最短双调旅程P(i,j)在到达终点P[j]之前，正常来说，按照双调的概念，一定经过了一个其x坐标刚好比点P[j]小的点，也就是P[j-1](当然当i=j-1时就另当别论了),所以如果当i
这相当于我们每次求解问题P(i,j)，都作了一次选择，要么是点P[j-1]或是点P[k]作为P[j]的前一个点，其示意图如下：
要知道，我们要求解的问题结果是b[n,n],于是
b[n,n]=b[n-1,n]+distance(n-1,n)；
这里要注意的一点，在之前的公式中，并不涉及求解类似b[i,i]的值,这里定义了b[i,i]的情况。
除此之外，还涉及到了对最优解的重构的问题。我们将使用一个r[i][j]数组表示子问题P(i,j)在到达终点P[j]之前经过的一个点P[k]对应的k值（仅挨着点P[j]的点），则子问题的解可以组织为其更小的子问题P（i，k）的解加上点P[k]和点P[j]。由之前的解题思路可知，对于问题P(i,j),当i=j-1时，k
其实得到的最优解是个闭合旅程，所以从出发后的第一个点与到达之前的一个点的位置是等价的。如闭合旅程是，也可以是。
构造解的过程如下：
每次加入的点总是在序号大的点下，因为问题P(i,j)总是分解为子问题P(i,k),不管k是等于j-1，还是小于j-1，然后确定点P[k]是到达P[j]之前的一个点，这也是问题每次选择的结果。使用一个数组存放序号，一边从0开始，一边从末尾开始。
以下是问题的实现：
#include&&#include&&#include&&using&namespace&&&#define&N&7&struct&Point{&&&&&double&x;&&&&&double&y;&};&struct&Point&points[N+1];&double&b[N+1][N+1];&int&r[N+1][N+1];&&&double&distance(int&i,int&j);//第i，j点的欧式距离&double&Euclidean_TSP();//最短闭合旅程长度&void&my_print_path();//打印旅程&&void&main(int&argc,&char&**argv){&&&&&ifstream&&&&&&infile.open("input.txt");//读入一个有各点坐标的文档&&&&&if&(!infile)&&&&&{&&&&&&&&&cout&&"error!"&&&&&}&&&&&int&i=1;&&&&&while&(infile&&points[i].x&&points[i].y)&&&&&{&&&&&&&&&i++;&&&&&}&&&&&cout&&"最短双调闭合旅程长度是："&&&&&my_print_path();&}&&double&distance(int&i,int&j){&&&&&return&sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x)&&&&&&&&&+(points[i].y-points[j].y)*(points[i].y-points[j].y));&}&&double&Euclidean_TSP(){&&&&&b[1][2]=distance(1,2);//最小的子问题&&&&&&&&&&for&(int&j=3;j&=N;j++)&&&&&{&&&&&&&&&//i=1时的情况&&&&&&&&&for&(int&i=1;i&&&&&&&&{&&&&&&&&&&&&&b[i][j]&=&b[i][j-1]+distance(j-1,j);&&&&&&&&&&&&&r[i][j]&=&j-1;&&&&&&&&&}&&&&&&&&&//i=j-1的情况&&&&&&&&&b[j-1][j]&=&b[1][j-1]+distance(1,j);//先设初值为k=1时的值&&&&&&&&&r[j-1][j]&=&1;&&&&&&&&&for&(int&k=1;k&&&&&&&&{&&&&&&&&&&&&&double&q&=&b[k][j-1]+distance(k,j);&&&&&&&&&&&&&if&(q&&&b[j-1][j])&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&b[j-1][j]&=&q;&&&&&&&&&&&&&&&&&r[j-1][j]&=&k;&&&&&&&&&&&&&}&&&&&&&&&}&&&&&}&&&&&b[N][N]&=&b[N-1][N]+distance(N-1,N);&&&&&return&b[N][N];&}&&void&my_print_path(){&&&&&int&string[N];&&&&&string[0]=N;&&&&&string[1]=N-1;&&&&&int&k=N-1;&&&&&int&left_hand=N-1,right_hand=N,begin=2,end=N-1;&&&&&for&(int&i=N-1,j=N;k!=1;)&&&&&{&&&&&&&&&k=r[i][j];&&&&&&&&&if&(left_hand&right_hand)&//比较那边的点的序号大&&&&&&&&{&&&&&&&&&&&&&left_hand=k;&&&&&&&&&&&&&string[begin]=k;&&&&&&&&&&&&&begin++;&&&&&&&&&}else{&&&&&&&&&&&&&right_hand=k;&&&&&&&&&&&&&string[end]=k;&&&&&&&&&&&&&end--;&&&&&&&&&}&&&&&&&&&if&(i==j-1)&&&&&&&&&{&&&&&&&&&&&&&j=i;&&&&&&&&&&&&&i=k;&&&&&&&&&}else&if&(i&&&&&&&&{&&&&&&&&&&&&&j=k;&&&&&&&&&}&&&&&}&&&&&cout&&"该旅程是：";&&&&&for&(int&index=0;index&&&&{&&&&&&&&&cout&&&&&}&&&&&cout&}&
input.txt:
最短双调闭合旅程长度是：25.584
该旅程是：7643125
其实旅程也可以是7521346
&本文出自 “” 博客，请务必保留此出处
发表评论：
TA的最新馆藏[转]&[转]&UVA - 1347 Tour 双调欧几里得旅行商有关问题 - 编程当前位置:& &&&UVA - 1347 Tour 双调欧几里得旅行商有关问题UVA - 1347 Tour 双调欧几里得旅行商有关问题&&网友分享于：&&浏览：0次UVA - 1347 Tour 双调欧几里得旅行商问题题目大意：给出n个点，要求你从最左边那个点走到最右边那个点，每个点都要被遍历过，且每个点只能走一次，问形成的最短距离是多少
解题思路：用dp[i][j]表示第一个人走到了第i个点，第二个人走到了第j个点且已经遍历了1–max(i,j)的所有点的最短距离。因为dp[i][j] = dp[j][i]的，所以我们设i & j的
当j & i-1 时，dp[i][j] = dp[i-1][j] + dis(i, i -1)
i + 1时情况就比较特别了,这里将j用i－1代替
dp[i][i - 1] = min(dp[i][i-1], dp[i-1][k] + dis(k,j))
具体的证明可以去百度查找：双调欧几里得旅行商问题
还有另一种写法我还是不懂
#include&cstdio&
#include&algorithm&
#include&cstring&
#include&cmath&
using namespace std;
const int N = 1010;
const double INF = 0x3f3f3f3f3f3f3f3f;
double dp[N][N], dis[N][N];
struct point{
double distance(int a, int b) {
return sqrt( (P[a].x - P[b].x) * (P[a].x - P[b].x) + (P[a].y - P[b].y) * (P[a].y - P[b].y));
void init() {
for(int i = 1; i &= i++)
scanf("%lf%lf", &P[i].x, &P[i].y);
for(int i = 1; i &= i++)
for(int j = 1; j &= j++)
dis[i][j] = dis[j][i] =
distance(i,j);
double solve() {
dp[2][1] = dis[2][1];
for(int i = 3; i &= i++) {
dp[i][i-1] = INF;
for(int j = 1; j & i - 1; j++) {
dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis[j][i]);
dp[i][j] = dp[i-1][j] + dis[i][i-1];
double ans = INF;
for(int i = 1; i & i++)
ans = min(ans, dp[n][i] + dis[i][n]);
int main() {
while(scanf("%d", &n) != EOF && n) {
printf("%.2lf\n", solve());
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 1234567891011 Copyright & &&版权所有uva 1347 - Tour(双调欧几里得旅行商问题） - 推酷
uva 1347 - Tour(双调欧几里得旅行商问题）
题目大意：给出n个点，确定一条
连接各点的最短闭合旅程的问题。
解题思路：dp[i][j]表示说从i联通到1，再从1联通到j的距离。
dp[i][j] = dp[i-1][j] + dis(i,i-1);
dp[i][i-1] = min (dp[i][i-1], dp[i-1][j] + dis(i, j));
#include &stdio.h&
#include &string.h&
#include &math.h&
#include &algorithm&
const int N = 105;
const double INF = 0x3f3f3f3f3f3f3f3f;
double x[N], y[N], dp[N][N];
inline double dis (int a, int b) {
return sqrt((x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]));
void init () {
for (int i = 1; i &= i++)
scanf(&%lf%lf&, &x[i], &y[i]);
memset(dp, 0, sizeof(dp));
dp[2][1] = dis(1, 2);
double solve () {
for (int i = 3; i &= i++) {
dp[i][i-1] = INF;
for (int j = 1; j & i-1; j++) {
dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis(i, j));
dp[i][j] = dp[i-1][j] + dis(i, i-1);
double ans = INF;
for (int i = 1; i & i++)
ans = min(ans, dp[n][i] + dis(n, i));
int main () {
while (scanf(&%d&, &n) == 1) {
printf(&%.2lf\n&, solve ());
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致　　欧几里得旅行商问题 是对平面上给定的n个点确定一条连接各点的最短闭合旅程的问题。图a给出了7个点问题的解，这个问题的一般形式是NP完全的,故其解需要多于多项式的时间。
　　J.K.Bentley建议通过只考虑双调旅程来简化问题，这种旅程即为从最左点开始，严格从左到最右点，再严格地从最右点回到最左点。图b显示了同样的7个点的问题的最短双调路线，在这种情况下，多项式的时间的算法是有可能的。
　　描述一个确定最优双调路线的O（n^2）时间的算法。可以假设任何两点的x坐标都不相同。
　　读了很多遍这个题，也看了网上好几篇关于这个问题的博客，有很多一部分是错误的却没有更正，于是自己实践整理了一份这个问题的解法。首先最大的疑惑在于理解什么叫做双调（Bitonic），读了很多解释的词条大概了解了双调的用处，我所理解的双调在这道题之中的思路就是将整个闭合的路线一个点展开，因为题中要求的是从左端向右端扫描，再从右端扫描回来。那么不妨将最左端的点作为出发点开始进行计算（从右端完全一致，不再赘述）。
　　我们需要一个辅助的矩阵a[iLen+1][iLen+1]，和所有动态规划问题一样矩阵的大小都是问题的规模+1，整个的计算过程是从左端到右端，也就是我们计算的最短路经从左端向右端生长的过程，辅助矩阵a[i][j]指的是p[i]到p[1]和p[1]到p[i-1]&共通&的最短路径，计算过程只利用矩阵的下三角部分，所以使前一个索引小与后一个索引。首先，将iLen个点存储到一个结构体/类数组之中，用来存放所有的点的坐标，记作数组p，p1,p2之间的距离记作dist（p1,p2）。
核心思想：
1）（前提）当我们计算第i个点或者将它并入最短路径的时候，前1.2.3...i-1个点已经形成了一条最短路径。
2）若要计算a[i][j]，新加入的点p[j]的选择分支有三种，也就是路线规划&生长&情况有且只有三种：
　　（一）当j-1〉i时，根据第（1）条我们需要做的就是在辅助矩阵中已经形成的子最短路径加上新增的边（按定义必然是先添加在更长的那半部分路线）
　　　　　就有 a[i][j]=a[i][j-1]+dist(j-1,j);
　　（二）当j-1=i时，就是一次总结前面的子最短路径生成更长的新子最短路径的时候。
　　　　　表示为 a[i][j]=min{(a[k][j-1]+dist(k,j)) , (a[k-1][j-1])+dist(k-1,j)....}////k为遍历值
&　& （三）当j=i 时，将整个图形封闭起来需要最后的两条边，实质上是（二）过程的一个分支
　　　　　即& a[i][j]=min{(a[k][j-1]+dist(k,j)+dist(j-1.j)).....}/////////k为遍历值
#include&iostream&
#include&vector&
#include&cstdlib&
#include&cmath&
#define MAX_VALUE 99999
class Point{
Point(double px=0,double py=0)
:x(px),y(py){}////////Constructor & Default to be Zero
double dist(Point p1,Point p2){
return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
int main(){
const int iLen=7;
Point p[iLen+1];//// Pointer List
p[1]=Point(0,6);
p[2]=Point(1,0);
p[3]=Point(2,3);
p[4]=Point(5,4);
p[5]=Point(6,1);
p[6]=Point(7,5);
p[7]=Point(8,2);
//////////////To minimize the time of Debugging
We get parameters initialize
double a[iLen+1][iLen+1]={}; ////null-filled
for(int j=3;j&=iLj++){
for(int i=1;i&=j-2;i++){
a[i][j]=a[i][j-1]+dist(p[j-1],p[j]);
a[j-1][j]=MAX_VALUE;
for(int i=1;i&=j-2;i++){
a[j-1][j]=(a[i][j-1]+dist(p[i],p[j]))&a[j-1][j]?(a[i][j-1]+dist(p[i],p[j])):a[j-1][j];
double dMin=MAX_VALUE;
for(int i=2;i&=iLen-1;i++){
double tmp=a[i][iLen]+dist(p[i],p[iLen])+dist(p[iLen-1],p[iLen]);
if(tmp&dMin)dMin=
///////////dMin records the answer
std::cout&&dMin&&std::
阅读(...) 评论()