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

对一类动态规划问题的研究 湖南省长沙市第一中学 徐源盛 1 3 4 2 5 =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坐标的千分之一。 你的目标是射落所有彩蛋并使得分最高。 A B C 人 问题一 已射的彩蛋集合是不断增大的。 用f1[i][j]、f2[i][j]分别表示从起点出发已射落i到j这一段彩蛋，当前停留在彩蛋i、彩蛋j的最大得分。 1 2 3 4 人 f1[1][3] 1 2 3 4 人 f2[1][3] 问题一 考虑f1[1][3]，当前处于位置1。 可以由f1[2][3]沿着2-1走来。再射落1号彩蛋。 1 2 3 4 人 1 2 3 4 人 1 问题一 考虑f1[1][3]，当前处于位置1。 可以由f1[2][3]沿着2-1走来。再射落1号彩蛋。 可以由f2[2][3]沿着3-1走来。再射落1号彩蛋。 1 2 3 4 人 1 2 3 4 人 1 问题一 射击i的得分是yi-t*vi，t为当前时刻。 过去的决策影响了当前射击的费用。 如果新增一维时间t，状态过多。 过去是怎样的？ 当前 过去 未来会怎样呢？ 问题一 将-t*vi在射落i之前计算。 每次移动都要把未来会减少的得分计算在内。 射击i时再加上yi/1000。 人 i+1 i j 初始 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]的方程类似。 答案就是max(f1[1][n]，f2[1][n])。 时间复杂度O(n2)。 小结 当前射击的费用受到之前决策的影响。 如果新增状态t表示过去决策的影响，状态数将会无法承受。 改变“时间观”，从过去考虑当前，即从当前考虑未来，把当前决策对未来的影响算作当前决策费用，计算到当前状态。 当前决策对未来“行动”费用的影响 只与当前决策有关。 将费用提前计算 当前决策 对未来“行动” 的费用影响 只与当前决策有关 当前决策 对未来“行动” 的费用影响 不只与当前决策有关 将未来的费用 的一部分视作 当前决策费用 计算在当前的状态中 问题二（改编自NOI2008Trans） n个点构成一棵树，根为1，每个非根点i都有且仅有一个后继点Si，和一个可靠系数Ci 定义点i的可靠性为R(i)=Ci+ ，其中K1。Pj为后继是i的点。 你可以最多修改m个点的后继。目标是最大化R(1)。 问题二 考虑如何计算R(1)。 R(1)=R2*k+R3*k+C1 =C1+C2*k+C3*k+R4*k2+R5*k2+R6*k2 x对1的贡献为Cx*kd(x,1)。 1 2 4 5 6 3 CX ×k ×k ×k ×k ×k ×k 问题二 R(1)= 每次修改都应该把点的后继直接设置为1。 问题二 用f[i][j]表示以i为根的树中，分配了j次修改的最大贡献。 1 x y i 4 2 3 问题二 Ⅰ.如果不修改i后继 把j次修改分配到i的子树中。 然后加上i在当前状态下对1的贡献，Ci*kd(i,1) 1 x y i 4 2 3 问题二 Ⅱ.如果修改i的后继设置成1。 2.1如果i的子孙在之前并没修改过。 i及i的子孙到1的距离都减少了2。 贡献值为修改前的除以k2。 1 x y i 4 2 3 c2*k4+c3*k4+c4*k5+ci*k3 c2*k2+c3*k2+c4*k3+ci*k 问题二 Ⅱ.如果修改i的后继设置成1。 2.2如果点2的后继在之前已经被设置成了1 把点i的后继修改成点1的时候点2的距离并没有减少2。 点2的决策影响着改变点i后继的费用。 1 x y i 4 2 3 点2的距离一直是1 问题二 把点2对修改点i时的费用贡献在决策点2的时候计算。 如果修改的是i后继。 1 x y i 4 2 3 点2的距离变成2 问题二 把点2对修改点i时的费用贡献在决策点2的时候计算。 如果修改的是y后继。 点2的贡献与未来的情况有关。 取决于离它最近的被修改的祖先。 1 x y i 4 2 3 点2的距离变成3 问题二 再加一维状态d，假设在未来的决策导致点i的距离为d。 f[i][j][d]表示点