算法合集之《对一类动态规划问题的研究》.pdf

对一类动态规划问题的研究

湖南省长沙市第一中学徐源盛

【关键字】

动态规划费用提前计算假设未来决策

【摘要】

本文通过四道题目探讨了一种比较特殊的动态规划问题，即当前决策影响未
来“行动”的费用。如果当前决策对未来的影响只与当前决策有关，则直接将对
未来费用的影响，算作当前的决策费用计算，并通过状态传递；如果对未来的影
响还与未来的情况有关，则新增状态假设未来的情况，待到未来决策时直接使用
假设的状态。这就是本论文详细阐述的解题方法。

【正文】

在常规动态规划问题中，我们面临当前状态时“行动”造成的花费往往与这个
状态是同时计算的。例如在经典的石子合并问题中，规划方程为
f[i][j]=max{f[i][k]+f[k+1][j]}+w(i,j)，当我们计算f[i][j]时，才会把将i到j的石子全部
合并到一起这一“行动”的费用加进去。这很符合我们的思维习惯。
然而近年来频繁出现一类动态规划问题，在这类问题中，当前“行动”的费用
的一部分需要在之前决策时被计算并以状态的形式对当前状态造成影响。造成这
一独特的计算的原因就是当前的决策会对未来的“行动”费用造成影响。这类问题
构造方程往往比较困难，需要仔细分析原题，找到矛盾所在。

一、当前决策对未来“行动”的费用影响只与当前决策有关
比如在两男两女中选一男一女去执行任务，已知每个人的效率，希望总效率
最高。并且男A如果被选，所有女生的效率加7，如果男B被选，所有女生的效
率减7。在第一阶段选男A还是男B对第二阶段女生的效率有不同的影响，可以
将对女生的影响当做男生的“自身魅力”，即把男A的效率加7，男B的效率减
7。而我们实际上是把第二阶段的费用在第一阶段计算了。对于这类问题我们往
往将对未来“行动”的影响一并算做当前决策的费用。下面通过两道例题进行详细
阐述。
【问题一】Sue的小球(sdtsc2008)
Sue和Sandy最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且
充满刺激的大海上。Sue有一支轻便小巧的小船，然而，Sue的目标并不是当一
个海盗，而是要收集空中漂浮的彩蛋。Sue有一个秘密武器，只要她将小船划到
一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩
蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Sue要想得
到更多的分数，必须尽量在魅力值高的时候收集这个彩蛋，而如果一个彩蛋掉入
海中，它的魅力值将会变成一个负数，但这并不影响Sue的兴趣，因为每一个彩
蛋都是不同的，Sue希望收集到所有的彩蛋。
Sandy就没有Sue那么浪漫了，Sandy希望得到尽可能多的分数，为了解决
这个问题，他先将这个游戏抽象成了如下模型：
以Sue的初始位置所在水平面作为x轴。
一开始空中有N个彩蛋，对于第i个彩蛋，他的初始位置用整数坐标（xi,yi）
表示，游戏开始后，它匀速沿y轴负方向下落,速度为vi单位距离/单位时间。Sue
的初始位置为(x0,0)，Sue可以沿x轴的正方向或负方向移动，Sue的移动速度是
1单位距离/单位时间，使用秘密武器得到一个彩蛋是瞬间的，得分为当前彩蛋
的y坐标的千分之一。
现在，Sue和Sandy请你来帮忙，为了满足Sue和Sandy各自的目标，你决
定在收集到所有彩蛋的基础上，得到的分数最高。

输入文件

第一行为两个整数N,x0用一个空格分隔，表示彩蛋个数与Sue的初始位置。
第二行为N个整数xi，每两个数用一个空格分隔，第i个数表示第i个彩蛋
的初始横坐标。
第三行为N个整数yi，每两个数用一个空格分隔，第i个数表示第i个彩蛋
的初始纵坐标。
第四行为N个整数vi，每两个数用一个空格分隔，第i个数表示第i个彩蛋
匀速沿y轴负方向下落的的速度。

输出文件

一个实数，保留三位小数，为收集所有彩蛋的基础上，可以得到最高的分数。

样例

输入样例(ball.in的内容)：
30
-4-22
223026
198
输出样例(ball.out的内容)：
0.000

数据范围

N<=20，对于30%的数据。
N<=1000，对于100%的数据。
44
-10<=xi,yi,vi<=10，对于100%的数据。

【分析】
先把所有的点包括起点按x值排序，这样题目就变成从起点出发，每次可以

向左或向右走到最近的某个彩蛋，将其射落，设每个彩蛋第一次走到的时刻为ti，
答案就是∑(yi-ti*vi)，使答案最大。
我们注意到已射落的彩蛋集合是不断增大的，这样很容易想到用f1[i][j]、
f2[i][j]分别表示从起点出发已射落i到j这一段彩蛋，当前停留在i点、j点的最
大得分。考虑f1[i][j],即点i是当前射击的彩蛋，射击的得分与当前时刻挂钩，但
是当前的时刻是不能从f1[i][