动态规划与单调性
前言:动态规划与单调性是密不可分的一对兄弟。许多动态规划的题目由于其状态转移方
程的特殊性而具有决策或取值上的单调。而这些特殊性质经常成了重要的突破口。现在的试
题的发展趋势是多元化,发散化。单纯的动态规划很多时候受到了多方面的限制。这时候对
于单调性的发掘应用也就逐渐成了一个重要的课题。下面通过一些例题来领会这种思想。
(由于利用队列与斜率进行决策优化已经被分到了数据结构部分,所以这里不予赘述)
例一:服务机构设置问题(2006 年福建省选试题)
在一个按照南北方向划分成规整街区的城市里, n 个居民点分布在一条直线上的 n 个坐
标点(x1<x2<x3...)处。居民们希望在城市中至少选择 1 个,但不超过 k 个居民点建立服务
机构。
在每个居民点处,服务需求量为 wi(>=0),在该居民点设置服务机构的费用为
ci(>=0)。假设居民点 i 到距其最近的服务机构的距离为 di ,则此居民点的服务费用为
di*wi。
建立 k 个服务机构的总费用为 A+B。A 是在 k 个居民点设置服务机构的费用的总和;B 是
n 个居民点服务费用的总和。
任务:
对于给定直线 L 上的 n 个点 ,编程计算在直线 L 上最多设置 k 处服务机构的最小总费用。
注:N<=1000
分析:
这个问题使我们想起了动态规划的一个经典模型:邮局问题。这里只是将此题加权。于是
仿照邮局问题我们很容易的就能得到如下状态转移方程:
设 f[i,j]为在 1..i 号居民点上设立 j 个服务机构,且第 j 号服务机构设在第 i 号居民点上的
最小费用。
f[i,j]=minimal(f[k,j-1]+value(k+1,j))+c[j]
其中 1<=k<=i-1,value(k+1,j)为第 k 与第 j 两个居民点上的两个服务机构相邻时,第 k+1
到第 j 这些居民点的最小服务费用。通过 O(n^2)的预处理可以算出来。
这个方程是 O(n^3)的,显然会超时。我们需要寻求一些优化方案。
我们设 s[i,j]为 f[i,j]取到最小值时的 k(即 f[i,j]的决策)。我们来观察 s[i,j]的单调情况。
I> s[i,j]<s[i+1,j] 解释:从直观上说,我们要把 j 个服务机构“平均”的分到一些居民点上,
肯定要处理的居民点数越多,服务机构位置越靠后。
II> s[i,j]>s[i,j-1] 解释:从直观上说,我们要把一些服务机构“平均”的分到 i 个居民点上,
肯定要处理的服务机构数越多,其位置越靠后。
以上的两个结论都可以用数学方法进行严格证明,这里略去。在考场上我们还可以将 s 数
组排成方阵输出,也可以方便的通过观察规律来获得以上结论。
我们将 i> ii>合起来,得到一个很重要的式子:s[i,j-1]<s[i,j]<s[i+1,j]
这个式子告诉我们:每个决策都是有一个范围的,而不必从头扫到尾。现在的问题是我
们如何在计算某个 f[i,j]之前得到其决策的范围。
其实非常方法简单:调整计算顺序。我们在外循环内从小到大计算 j,在内循环内从大到
小计算 i,那么我们就可以保证在 f[i,j]被计算出以前 s[i,j-1]与 s[i+1,j]都是已知的。
从程序上来看,虽然表面上还是三重循环,实际上的运行效果非常的好。时间复杂度大
约在 O(n^2)~O(n^2logn)左右。这个题目被很好的解决了。