《守望者的逃离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.