当前位置: 代码迷 >> 综合 >> POJ1160 邮局问题
  详细解决方案

POJ1160 邮局问题

热度:5   发布时间:2024-01-16 14:00:58.0

题意:

m个村庄排在同一直线上,在之中建立n个邮局,要求这些村庄到最近的邮局之和最小

要点:

这道题挺难的,思路比较难想到不说还比较难理清

首先:在第a个和第b个村庄中建1个邮局的邮费最小方案应该是建在第(a+b)/2个村庄里,说实在的这个我一开始都不知道。

然后问题就可以拆成DP问题:在前k个村庄中建i-1个邮局加在第k+1到第j个村庄中建1个邮局,这就是一个典型的DP问题了。状态转移方程为dp[i][j]=min(d[i][j],dp[i-1][k]+sum[k+1][j]),说白了就是求dp[i][j]在j=k到v的最小值。注意k要从i-1开始,因为前i个村庄建i个邮局的情况也要考虑到。

看起来比较难以理解,其实把sum数组看成一般的a数组,就是一个数塔问题,仔细想想其实就是稍微变化了一下,跟花店问题是同一类型的题。

学到了abs()函数,这个函数的作用是取绝对值,头文件是stdlib.h和math.h

代码如下:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define inf 0xffffffint main()
{int v, p,i, j,k;int dp[500][500];int a[500], sum[500][500];while (scanf("%d%d", &v, &p) != EOF){memset
  相关解决方案