动态规划与单调性
前言：动态规划与单调性是密不可分的一对兄弟。许多动态规划的题目由于其状态转移方
程的特殊性而具有决策或取值上的单调。而这些特殊性质经常成了重要的突破口。现在的试
题的发展趋势是多元化，发散化。单纯的动态规划很多时候受到了多方面的限制。这时候对
于单调性的发掘应用也就逐渐成了一个重要的课题。下面通过一些例题来领会这种思想。
（由于利用队列与斜率进行决策优化已经被分到了数据结构部分，所以这里不予赘述）
例一：服务机构设置问题（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)左右。这个题目被很好的解决了。
评论0