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

《国家集训队2009论文集对一类动态规划问题的》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对一类动态规划问题的研究湖南省长沙市第一中学徐源盛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

2、人问题一已射的彩蛋集合是不断增大的。用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*v

3、i，t为当前时刻。过去的决策影响了当前射击的费用。如果新增一维时间t，状态过多。过去是怎样的？当前过去未来会怎样呢？问题一将-t*vi在射落i之前计算。每次移动都要把未来会减少的得分计算在内。射击i时再加上yi/1000。人i+1ij初始i初始问题一用w[i][j]表示除了i到j这段彩蛋的下落速度和。从i+1走到i，f1[i][j]=f1[i+1][j]-(xi+1-xi)*w[i+1][j]从j走到i，f1[i][j]=f2[i+1][j]-(xj-xi)*w[i+1][j]f1[i][j]+=yi/1000。f2[i][j]

4、的方程类似。答案就是max(f1[1][n]，f2[1][n])。时间复杂度O(n2)。小结当前射击的费用受到之前决策的影响。如果新增状态t表示过去决策的影响，状态数将会无法承受。改变“时间观”，从过去考虑当前，即从当前考虑未来，把当前决策对未来的影响算作当前决策费用，计算到当前状态。当前决策对未来“行动”费用的影响只与当前决策有关。将费用提前计算当前决策对未来“行动”的费用影响只与当前决策有关当前决策对未来“行动”的费用影响不只与当前决策有关将未来的费用的一部分视作当前决策费用计算在当前的状态中问题二（改编自NOI2008Tr

5、ans）n个点构成一棵树，根为1，每个非根点i都有且仅有一个后继点Si，和一个可靠系数Ci定义点i的可靠性为R(i)=Ci+，其中K<1。Pj为后继是i的点。你可以最多修改m个点的后继。目标是最大化R(1)。问题二考虑如何计算R(1)。R(1)=R2*k+R3*k+C1=C1+C2*k+C3*k+R4*k2+R5*k2+R6*k2x对1的贡献为Cx*kd(x,1)。124563CX×k×k×k×k×k×k问题二R(1)=每次修改都应该把点的后继直接设置为1。问题二用f[i][j]表示以i为根的树中，分配了j次修改的最大贡献。1x

6、yi423尝试！问题二Ⅰ.如果不修改i后继把j次修改分配到i的子树中。然后加上i在当前状态下对1的贡献，Ci*kd(i,1)1xyi423问题二Ⅱ.如果修改i的后继设置成1。2.1如果i的子孙在之前并没修改过。i及i的子孙到1的距离都减少了2。贡献值为修改前的除以k2。1xyi423c2*k4+c3*k4+c4*k5+ci*k3c2*k2+c3*k2+c4*k3+ci*k问题二Ⅱ.如果修改i的后继设置成1。2.2如果点2的后继在之前已经被设置成了1把点i的后继修改成点1的时候点2的距离并没有减少2。点2的决策影响着改变点i后继的

7、费用。1xyi423点2的距离一直是1难道用二进制状态表示i每个子孙的修改情况？问题二把点2对修改点i时的费用贡献在决策点2的时候计算。如果修改的是i后继。1xyi423点2的距离变成2问题二把点2对修改点i时的费用贡献在决策点2的时候计算。如果修改的是y后继。点2的贡献与未来的情况有关。取决于离它最近的被修改的祖先。1xyi423点2的距离变成3问题二再加一维状态d，假设在未来的决策导致点i的距离为d。f[i][j][d]表示点i为根的树中，修改j次，且点i到1的距离为d的最大贡献值。i的儿子j的距离只能为d+1或者1。i1d

8、jd+1j1g[i][j][d]=max{f[i][j][d+1],f[i][j][1]}问题二转移f[i][j][d]。如果i不修改后继,那么d>1。f[i][j][d]=max{g[s1][j1][d]+g[s2][j2][d]+……+g[st][jt][d