《守望者的逃离noip2007——解题报告》由会员分享，可在线阅读，更多相关《守望者的逃离noip2007——解题报告（7页珍藏版）》请在金锄头文库上搜索。
1、守望者的逃离（守望者的逃离（NOIP2007NOIP2007）【题目描述题目描述】恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族 企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。 为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那 时，岛上的所有人都会遇难。守望者的跑步速度为 17m/s，以这样的速度是无 法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在 1s 内移动 60m，不过每次 使用闪烁法术都会消耗魔法值 10 点。守望者的魔法值恢复的速度为 4 点/s，只 有处在原地休息状态时才能恢复。现在已知守望者的魔法初值 M，他所在的初始
2、位置与岛的出口之间的距离 S，岛沉没的时间 T。你的任务是写一个程序帮助守望者计算如何在最短的时间 内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注 意：守望者跑步、闪烁或休息活动均以秒(s)为单位，且每次活动的持续时间为 整数秒。距离的单位为米(m)。【输入描述输入描述】仅一行，包括空格隔开的三个非负整数 M, S, T【输出描述输出描述】包含两行：第 1 行为字符串“Yes”或“No”（区分大小写），即守望者是否能逃离荒岛。第 2 行包含一个整数。第一行为“Yes”（区分大小写）时表示守望者逃离荒岛 的最短时间；第一行为“No”（区分大小写）时表示守望者能走的最远距离。
3、【样例样例】输入39 200 4 输出No 197 【限制限制】 30%的数据满足: 1 =120，就等 5s，闪两次。 计算并比较跑步与闪烁的时间： 回复+闪烁：共耗时 7S，前进了 120 米 跑步：717=119 米 因此用去的时间 tt=tt+7；行走的距离为 ss：ss=ss+120;当 tt=t-7 时，ss=2 时， 应当放弃采用此策略。 （因为此时，我们可以等的 1 秒或是 2 秒就可以闪了。 ）如果 t- tt=34) and (m=6) and (t-tt=2)，那么就选择闪烁，等一秒，闪一秒。 魔法减 6。 4：如果 (s-ss=51) and (m=2 ) and (t
4、-tt=3) ，那么就选择闪烁，等两秒，闪一秒， 魔法减 2。 5：如果以上的到的结果的都不能跑出来，那么就选择跑路吧。最后判断能否跑出。 具体实现，见参考程序 3我们可以这样想： 贪心为的是什么？局部 最优全局最优，其条 件是每一步都选择最优 解，而动规呢？动规说 白了就是局部最优不能 一步达到全局最优，你 得走一步看一步，对不 对？【参考程序参考程序】 1 1、 简单动规（只是思路，给个大框，如果有能力的读者请越过）简单动规（只是思路，给个大框，如果有能力的读者请越过） program Devil_Hunter; var f:array0.1000,0.1000 of integer;M,
5、S,T:integer;i,j,k,maxf:integer; function max(a1,a2,a3:integer):integer; beginmax:=0;if a1=max then max:=a1;if a2=max then max:=a2;if a3=max then max:=a3; end; beginassign(input,data.in);assign(output,data.out);reset(input);rewrite(output);readln(M,S,T);fm,0:=s;for i:=0 to M dofor j:=0 to T dobeginif
6、 i=10 then fi,j:=max(fi,j-1+17,fi-10,j-1+60,fi+4,j-1)else fi,j:=max(fi,j-1+60,fi+4,j-1,0);end;maxf:=0;for k:=1 to M do if fk,T=maxf then maxf:=fk,T;if maxf=S then writeln(Yes) else writeln(No);close(input);close(output); end. 2 2、 完整动规（此方法的缺憾就是数据太大的话，超时严重，预计得分完整动规（此方法的缺憾就是数据太大的话，超时严重，预计得分 6060） prog
7、ram a3(input,output); var a,b:array0.10000of longint; m,s,t,i,j:longint; function max(a,b,c:longint):longint; 三个数找最大值 var k:longint; begin if ab then k:=a else k:=b; if k max:=k; end; begin assign(input,escape.in); assign(output,escape.out); reset(input); rewrite(output); readln(m,s,t); for i:=0 to
8、10000 do 数组清 0 beginai:=0; bi:=0; end; for i:=1 to t do begin for j:=0 to 9 do begin bj:=max(aj+17,aj+4,0); 动态规划 if bj=s then begin writeln(Yes); 找到最小解，提前退出 writeln(i); close(input); close(output); halt; end; end; for j:=10 to m do begin bj:=max(aj+17,aj+4,aj-10+60); 动态规划 if bj=s then begin writeln(
9、Yes); 找到最小解，提前退出 writeln(i); close(input); close(output); halt; end; end; a:=b; end; writeln(No); 无解 writeln(am); close(input); close(output); end. 3 3、 贪心的方法（预计得分贪心的方法（预计得分 100100） program Devil_Hunter3; var m,s,t,ss,tt:longint; begin assign(input,escape.in);reset(input); assign(output,escape.out);
10、rewrite(output); read(m,s,t); ss:=0;tt:=0; while m=10 dobegindec(m,10);inc(ss,60);inc(tt);if (ss=s) and (t=tt) thenbeginwriteln(Yes);write(tt);close(output);halt;end;if ttt then begindec(tt);dec(ss,60);inc(m,10);break;end;end;while (s-ss=120) dobegininc(tt,7);ss:=ss+120;if t=tt thenbeginif m=2 thenb
11、egindec(tt,7);ss:=ss-120;end;break;end;if t=s) and (t=tt) thenbeginwriteln(Yes);write(tt);close(output);halt;end;while (s-ss=34) and (m=6) and (t-tt=2) dobegininc(tt,2);dec(m,6);inc(ss,60);end;while (s-ss=51) and (m=2 ) and (t-tt=3) dobegininc(tt,3);dec(m, 2);inc(ss,60);end; if (ss=s) and (t=tt) the
12、nbeginwriteln(Yes);write(tt);close(output);halt;end; repeatinc(tt);inc(ss,17);if (ss=s) and (t=tt) thenbeginwriteln(Yes);write(tt);close(output);halt;end;if ttt then begindec(tt);dec(ss,17);break;end; until false; writeln(No); write(ss); close(output); end. 4 4、 动规的优化（预计得分动规的优化（预计得分 100100） program
13、Devil_Hunter4(input,output); var m,s,t,ti:longint; ms:array1.2,0.300000 of longint; ts:array0.300000 of longint; begin assign(input,escape.in); assign(output,escape.out); reset(input); rewrite(output); readln(m,s,t); ms2,0:=m; ts0:=0; for ti:=1 to t do begin if ms2,ti-1=10 then begin ms1,ti:=ms1,ti-1+60; ms2,ti:=ms2,ti-1-10; end else begin ms1,ti:=ms1,ti-1; ms2,ti:=ms2,ti-1+4; end; if tsti-1+17ms1,ti then tsti:=tsti-1+17 else tsti:=ms1,ti; if tsti=s then begin writeln(Yes); writeln(ti); close(input); close(output); halt; end; end; writeln(No); writeln(tst); close(input); close(output); end.
