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

《算法合集之《对一类动态规划问题的研究》》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、对一类动态规划问题的研究湖南省长沙市第一中学徐源盛【关键字】动态规划费用提前计算假设未来决策【摘要】本文通过四道题目探讨了一种比较特殊的动态规划问题，即当前决策影响未来“行动”的费用。如果当前决策对未来的影响只与当前决策有关，则直接将对未来费用的影响，算作当前的决策费用计算，并通过状态传递；如果对未来的影响还与未来的情况有关，则新增状态假设未来的情况，待到未来决策时直接使用假设的状态。这就是本论文详细阐述的解题方法。【正文】在常规动态规划问题中，我们面临当前状态时“行动”造成的花费往往与这个状态是同时计算的。例如在经典的石子合并问题中，规划方程为f[i][j]=max{f[i][k]+f

2、[k+1][j]}+w(i,j)，当我们计算f[i][j]时，才会把将i到j的石子全部合并到一起这一“行动”的费用加进去。这很符合我们的思维习惯。然而近年来频繁出现一类动态规划问题，在这类问题中，当前“行动”的费用的一部分需要在之前决策时被计算并以状态的形式对当前状态造成影响。造成这一独特的计算的原因就是当前的决策会对未来的“行动”费用造成影响。这类问题构造方程往往比较困难，需要仔细分析原题，找到矛盾所在。一、当前决策对未来“行动”的费用影响只与当前决策有关比如在两男两女中选一男一女去执行任务，已知每个人的效率，希望总效率最高。并且男A如果被选，所有女生的效率加7，如果男B被选，所有女生

3、的效率减7。在第一阶段选男A还是男B对第二阶段女生的效率有不同的影响，可以将对女生的影响当做男生的“自身魅力”，即把男A的效率加7，男B的效率减7。而我们实际上是把第二阶段的费用在第一阶段计算了。对于这类问题我们往往将对未来“行动”的影响一并算做当前决策的费用。下面通过两道例题进行详细阐述。【问题一】Sue的小球(sdtsc2008)Sue和Sandy最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上。Sue有一支轻便小巧的小船，然而，Sue的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋。Sue有一个秘密武器，只要她将小船划到一个彩蛋的正下方，然后使用秘密武器便可以

4、在瞬间收集到这个彩蛋。然而，彩蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Sue要想得到更多的分数，必须尽量在魅力值高的时候收集这个彩蛋，而如果一个彩蛋掉入海中，它的魅力值将会变成一个负数，但这并不影响Sue的兴趣，因为每一个彩蛋都是不同的，Sue希望收集到所有的彩蛋。Sandy就没有Sue那么浪漫了，Sandy希望得到尽可能多的分数，为了解决这个问题，他先将这个游戏抽象成了如下模型：以Sue的初始位置所在水平面作为x轴。一开始空中有N个彩蛋，对于第i个彩蛋，他的初始位置用整数坐标（xi,yi）表示，游戏开始后，它匀速沿y轴负方向下落,速度为vi单位距离/单位时间。Sue

5、的初始位置为(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个数表

6、示第i个彩蛋匀速沿y轴负方向下落的的速度。输出文件一个实数，保留三位小数，为收集所有彩蛋的基础上，可以得到最高的分数。样例输入样例(ball.in的内容)：30-4-22223026198输出样例(ball.out的内容)：0.000数据范围N<=20，对于30%的数据。N<=1000，对于100%的数据。44-10<=xi,yi,vi<=10，对于100%的数据。【分析】先把所有的点包括起点按x值排序，这样题目就变成从起点出发，每次可以向左或向右走到最近的某个彩蛋，将其射落，设每个彩蛋第一次走到的时刻为ti，答案就是∑(yi-ti*vi)，使答案最大。我们注意到已射落的彩蛋集合是不断增

7、大的，这样很容易想到用f1[i][j]、f2[i][j]分别表示从起点出发已射落i到j这一段彩蛋，当前停留在i点、j点的最大得分。考虑f1[i][j],即点i是当前射击的彩蛋，射击的得分与当前时刻挂钩，但是当前的时刻是不能从f1[i][j]的状态中表示出来的。如果我们再添一维状态表示时间，这样时间复杂度是不允许的。我们发现上述方法的矛盾其实就在于曾经的行走方案会对当前射击的得分产生影响，我们可以进一步考虑f1[i][j]的求解，由于