国家集训队2009论文集对一类动态规划问题的.ppt

文档介绍：对一类动态规划问题的研究湖南省长沙市第一中学徐源盛13425=max{f[i][k]+f[k+1][j]}+f[i][j]w(i,j)F[2][4]W[2][4]引入当前状态的“行动”花费与这个状态同时计算引入男A男B女A女B+7+7引入男A男B女A女B-7-7+7-7问题一有n个彩蛋,分别位于(xi,yi),以vi的速度匀速下落。你从坐标x出发,速度为1,每次可以向左或向右走到一个未被射落的彩蛋,将其射落。得分为被射彩蛋y坐标的千分之一。你的目标是射落所有彩蛋并使得分最高。ABC人问题一已射的彩蛋集合是不断增大的。用f1[i][j]、f2[i][j]分别表示从起点出发已射落i到j这一段彩蛋,当前停留在彩蛋i、彩蛋j的最大得分。1234人f1[1][3]1234人f2[1][3]问题一考虑f1[1][3],当前处于位置1。可以由f1[2][3]沿着2->1走来。再射落1号彩蛋。1234人1234人1问题一考虑f1[1][3],当前处于位置1。可以由f1[2][3]沿着2->1走来。再射落1号彩蛋。可以由f2[2][3]沿着3->1走来。再射落1号彩蛋。1234人1234人1问题一射击i的得分是yi-t*vi,t为当前时刻。过去的决策影响了当前射击的费用。如果新增一维时间t,状态过多。过去是怎样的?当前过去未来会怎样呢?问题一将-t*vi在射落i之前计算。每次移动都要把未来会减少的得分计算在内。射击i时再加上yi/1000。人i+1ij初始i初始