问题 5087 --守望者的逃离-NOIP2007PJT3

5087: 守望者的逃离-NOIP2007PJT3

时间限制: 1 Sec  内存限制: 128 MB
提交: 27  解决: 21
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][84kb]

题目描述

守望者的逃离

escape.pas/c/cpp

题目描述

恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵,率深藏在海底的那加企图叛变:守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去,到那时,刀上的所有人都会遇难:守望者的跑步速度,为17m/s, 以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术,可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4/s,只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M,他所在的初始位置与岛的出口之间的距离S,岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛,若不能逃出,则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)


输入格式

输入文件escape.in仅一行,包括空格隔开的三个非负整数MST


输出

输出文件escape.out包含两行:

1行为字符串"Yes""No" (区分大小写),即守望者是否能逃离荒岛。

2行包含一个整数,第一行为"Yes" (区分大小写)时表示守望着逃离荒岛的最短时间

第一行为"No" (区分大小写时表示守望者能走的最远距离。


样例输入

39 200 4

样例输出

No
197

数据范围

30%的数据满足: 1 <= T<= 10, 1 <=S<= 100

50%的数据满足: 1 <= T <= 1000, 1 <= S <= 10000

100%的数据满足: 1 <= T <= 300000, 0 <= M<=1000 1 <=S <= 10^8

输入

输出

提示


题解A.一般做法是用贪心加动规。



贪心策略:(注意,顺序不能反!)



   1: 如果有魔法,先放法。



2:如果剩下的距离>=120,就等5s,闪两次。共耗时7S,前进了120米,比跑7s走的远(7×17=119)即,用去的时间tt=tt+7;行走的距离为ss:ss=ss+120;当tt=t-7时,ss<s时,m>=2时,应当放弃采用此策略。(因为此时,我们可以等的1秒或是2秒就可以闪了。)如果t-tt<7,放弃此策略。



    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:如果以上的到的结果的都不能跑出来,那么就选择跑路吧。最后判断能否跑出。



题解B



典型的动态规划。

设f[i,j]为第i秒,魔法值为j时可行的最大距离。

f[i,j]:=max{f[i-1,j]+17,f[i-1,j-10]+60,f[i-1,j+4]} (当j≥10时);

f[i,j]:=max{f[i-1,j]+17,f[i-1,j+4]} (当j<10时)

按题目所说,最大魔法值为1000,最大时间为300000秒,那么需要300000000的数组,空间会溢出,所以使用两个一维数组来迭代,只需2000的数组,但是时间复杂度为O(t*m),有可能会超时

【深入思考】

前面的动态规划时间复杂度太高,是否能想出更优的算法呢?思考一下,可以发现,中间的过程无非就是闪烁加恢复魔法,有时再走几步,我们用ms数组记录,闪烁加恢复魔法可走的最大距离,再和走路比较,选出最优方案,存入ts数组,这样的话,时间复杂度只有O(t),比前面的算法好得多。













来源

[提交][状态]