守望者的逃离noip2007解题报告.doc

守望者的逃离（NOIP2007） 【题目描述】 恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。 ??? 现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意：守望者跑步、闪烁或休息活动均以秒(s)为单位，且每次活动的持续时间为整数秒。距离的单位为米(m)。 仅一行，包括空格隔开的三个非负整数M,?S,?T包含两行： 第1行为字符串“Yes”或“No”（区分大小写），即守望者是否能逃离荒岛。 第2行包含一个整数。第一行为“Yes”（区分大小写）时表示守望者逃离荒岛的最短时间；第一行为“No”（区分大小写）时表示守望者能走的最远距离。39 200 4 输出 No 197 【限制】 30%的数据满足: 1 = T= 10， 1 =S= 100 50%的数据满足: 1 = T = 1000， 1 = S = 10000100%的数据满足: 1 = T = 300000， 0 = M=1000 1 =S = 10^8主线任务必须在3分半钟内逃出该洞穴,而且必须存活下来. 一个字,就是跑,多多利用的传送术,最好是有LV3,这样方便跑路,溜到开头的地方即可F[I,j]=max{f[I,j-1]+17,f[i+4,j-1]}具体实现过程我就不赘述了（见参考程序）。 终止的情况，我们只要考虑t 而不必考虑mana，因为mana好像你手里的票子，活着的时候省着花，你都快死了（或者说已经死了），留着还有啥用？这个东西又不能带进棺材，只要考虑j=t时f[1..i,t]的最大值（你最多能跑多远）或者说只要考虑f[0,t](这就是传说中死钱花光所有钱的跑法，这种人往往获得最潇洒！) *此方法参考程序见“参考程序2” 二、动规的优化（见参考程序4） 按题目所说，最大魔法值为1000，最大时间为300000秒，那么需要300000000的数组，空间会溢出，所以使用两个一维数组来迭代，只需2000的数组，但是时间复杂度为O(t*m)，有可能会超时。思考一下，可以发现，中间的过程无非就是闪烁加恢复魔法，有时再走几步，我们用ms数组记录，闪烁加恢复魔法可走的最大距离，再和走路比较，选出最优方案，存入ts数组，这样的话，时间复杂度只有O(t),比前面的算法好得多。 【贪心算法】 这道题还有一种经典的算法就是贪心，如果说动态规划的方法是走一步看一步的话，那贪心就是上来一下子把能花的钱（mana）都挥霍干净，看看自己跑出去没，没跑出去的话，看看自己离出口还有多远，很近的话——直接用跑的，要是远的话，那就恢复一下mana试试看 贪心策略： 1: 。2：如果剩下的距离=120，就等5s，闪两次。共耗时7S，前进了120米7×17=119米 因此用去的时间tt=tt+7；行走的距离为ss：ss=ss+120;当tt=t-7时，sss时，m=2时，应当放弃采用此策略。（因为此时，我们可以等的1秒或是2秒就可以闪了。）如果t-tt7，放弃此策略。 3：如果 （s-ss=34) and (m=6) and (t-tt=2)，那么就选择闪烁，等一秒，闪一秒。魔法减6。 4：如果?? (s-ss=51) and (m=2 ) and (t-tt=3) ，那么就选择闪烁，等两秒，闪一秒，魔法减2。5：如果以上的到的结果的都不能跑出来，那么就选择跑路吧。最后判断能否跑出。program Devil_Hunter; var f:array[0..1000,0..1000] of integer; M,S,T:integer; i,j,k,maxf:integer; function max(a1,a2,a3:integer):integer; begin max:=0; if a1=max then max:=a1; if a2=max then max:=a2; if a3=max then max:=a3; end; begin assign(input,data.in); assign(output,data.out); reset(in