搜索
对一类动态规划问题的研究湖南省长沙市第一中学徐源盛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初始问题一•用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)。wjjPRk1)(问题二•考虑如何计算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)。124563CX×k×k×k×k×k×k问题二•R(1)=•每次修改都应该把点的后继直接设置为1。njidkci1)1,(问题二•用f[i][j]表示以i为根的树中，分配了j次修改的最大贡献。1xyi423问题二•Ⅰ.如果不修改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后继的费用。1xyi423点2的距离一直是1问题二•把点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。i1djj1g[i][j][d]=max{f[i][j][d+1],f[i][j][1]}问题二•转移f[i][j][d]。•如果i不修改后继,那么d1。•f[i][j][d]=max{g[s1][j1][d]+g[s2][j2][d]+……+g[st][jt][d]}+c[i]*kd•j1+j2+…jt=j。s1,s2…st为i的t个儿子。•用FF[i][j]表示前i个儿子分配了j次修改的最大贡献。•FF[i][j]=FF[i-1][k]+g[si][j-k][d]。问题二•如果修改i的后继，那么d=1。•f[i][j][1]=max{g[s1][j1][1]+g[s2][j2][1]+……+g[st][jt][1]}+c[i]*k•j1+j2+…jt=j-1。s1,s2…st为i的t个儿子。•时间复杂度是O(n2*m2)。问题二•在树上进行动态规划，并且将本应该在点i计算的费用转化到点i的子孙决策时计算。•在规划i的子孙j时假设未来的情况，并以不同状态记录下来。•就好比是沿着不同的道路把费用传递到未来，等到规划点i时直接使用过去假设的决策。•IOI2005《河流》、NOI2006《网络收费》将费用提前计算当前决策对未来“行动”的费用影响只与当前决策有关当前决策对未来“行动”的费用影响不只与当前决策有关将未来的费用的一部分视作当前决策费用计算在当前的状态中新增状态假设未来总结当前状态过去状态2过去状态1未来状态未来状态影响未来状态影响未来状态附加费用附加费用附加费用附加费用