PKU1160邮局动态规划算法详解

需积分: 10 71 浏览量更新于2024-09-16 1 收藏 3KB TXT 举报

邮局PKU1160 动态规划动态规划是算法设计中的一种重要方法，能够解决许多复杂的问题。动态规划的核心思想是将问题分解成多个小问题，然后使用已知的结果解决当前问题。在这个问题中，我们需要解决的是邮局PKU1160的问题，这是一个经典的动态规划问题。问题的描述是：给定一个数组pos，数组中的每个元素表示邮局的位置，然后需要计算出每个邮局到达的最小成本。我们可以使用动态规划的方法来解决这个问题。首先，我们需要定义一个二维数组dp，其中dp\[i]\[j]表示从邮局i到邮局j的最小成本。然后，我们可以使用以下公式来计算dp\[i]\[j]： dp\[i]\[j] = min(dp\[i]\[j], dp\[k]\[j-1] + sum\[k+1]\[i]) 其中，sum\[i]\[j]表示从邮局i到邮局j的总成本。我们可以使用以下公式来计算sum\[i]\[j]： sum\[i]\[j] = sum\[i]\[j-1] + pos\[j] - pos\[(i+j)/2] 我们可以使用动态规划的方法来计算dp\[i]\[j]，从而解决这个问题。在代码中，我们首先定义了一个二维数组dp和sum，然后使用循环来计算dp\[i]\[j]和sum\[i]\[j]。最后，我们可以使用dp\[V]\[P]来计算出邮局PKU1160的最小成本。动态规划是一种非常重要的算法设计方法，它可以解决许多复杂的问题。在这个问题中，我们使用动态规划来解决邮局PKU1160的问题，并且可以使用这种方法来解决许多其他的动态规划问题。需要注意的是，在动态规划中，我们需要定义一个状态转移方程，以便计算出当前问题的结果。在这个问题中，我们使用了以下状态转移方程： dp\[i]\[j] = min(dp\[i]\[j], dp\[k]\[j-1] + sum\[k+1]\[i]) 这是一种常见的状态转移方程，用于计算出当前问题的结果。动态规划是一种非常重要的算法设计方法，它可以解决许多复杂的问题。在这个问题中，我们使用动态规划来解决邮局PKU1160的问题，并且可以使用这种方法来解决许多其他的动态规划问题。

公路旁的村庄有一个直的公路。高速公路表示为整数轴，每个村确定一个整数坐标位置。有在同一位置上没有两个村庄。两个位置之间的距离是整数坐标的差异的绝对值。邮政局将在一些建成，但不一定所有的村庄。在它的一个村庄，邮局有相同的立场。建设的邮政局，他们的立场，应选择，使每个村和其最近的邮局之间的所有距离的总和最小。你是写一个程序，给邮局的村庄和数量的立场，计算每个村和其最近的邮局之间的所有距离尽可能少的总和。

输入

你的计划是从标准输入读取。第一行包含两个整数：第一是村庄至五，1 <= [V] <= 300，二是邮政局磷，1 <= P <= 30，P均<=五，第二行包含以递增顺序V整数。这些V整数村庄的位置。对于每个位置X，它认为：1 <= x <= 10000。
产量

第一行包含一个整数S，这是每个村和其最近的邮局之间的所有距离的总和。
解析；
1、考虑在V个村庄中只建立【一个】邮局的情况，显然可以知道，将邮局建立在中间的那个村庄即可。也就是在a到b间建立一个邮局，若使消耗最小，则应该将邮局建立在（a+b)/2这个村庄上（可以通过画图知道）。

2、下面考虑建立【多个】邮局的问题，可以这样将该问题拆分为若干子问题，在前i个村庄中建立j个邮局的最短距离，是在前【k】个村庄中建立【j-1】个邮局的最短距离与在【k+1】到第i个邮局建立【一个】邮局的最短距离的和。而建立一个邮局我们在上面已经求出。

3、状态表示，由上面的讨论，可以开两个数组

dp[i][j]:在前i个村庄中建立j个邮局的最小耗费

sum[i][j]:在第i个村庄到第j个村庄中建立1个邮局的最小耗费

那么就有转移方程：dp[i][j] = min(dp[i][j],dp[k][j-1]+sum[k+1][i]) DP的边界状态即为dp[i][1] = sum[1][i]; 所要求的结果即为dp[vil_num][post_num];

4、然后就说说求sum数组的优化问题，可以假定有6个村庄，村庄的坐标已知分别为p1,p2,p3,p4,p5,p6;那么，如果要求sum[1][4]的话邮局需要建立在2或者3处,放在2处的消耗为p4-p2+p3-p2+p2-p1=p4-p2+p3-p1

放在3处的结果为p4-p3+p3-p2+p3-p1=p4+p3-p2-p1，可见，将邮局建在2处或3处是一样的。现在接着求sum[1][5],现在处于中点的村庄是3，那么1-4到3的距离和刚才已经求出了，即为sum[1][4],所以只需再加上5到3的距离即可。同样，求sum[1][6]的时候也可以用sum[1][5]加上6到中点的距离。所以有递推关系：sum[i][j] = sum[i][j-1] + p[j] -p[(i+j)/2]

#include <cstdio>

下载后可阅读完整内容，剩余2页未读，立即下载

fengtmg

粉丝: 0
资源: 1

PKU1160邮局动态规划算法详解

动态规划之邮局选址

POJ 1125 1157 1159 1160 1163 1179

./mwseg.pl ../gold/pku_training_words.txt < ../testing/pku_test.txt > pku_test_seg.txt

想在python中运行./mwseg.pl ../gold/pku_training_words.txt < ../testing/pku_test.txt > pku_test_seg.txt怎么操作

介绍PKU-MMD数据集

pku-vd数据集特点

pku-nip-lab

pku vehicleid dataset

pku_law_selenium这个模块是我自己的

最新资源