切换到宽版
  • 12691阅读
  • 10回复

谁会今年普及组第三题 [复制链接]

上一主题 下一主题
离线dqllsc
 
只看楼主 倒序阅读 0 发表于: 2007-11-18
帖一帖吧
各为大牛
离线kickkill
只看该作者 1 发表于: 2007-11-18
我的算法只有50分……
离线zhousi
只看该作者 2 发表于: 2007-11-18
program a3(input,output);
var
  a,b:array[0..10000]of longint;
  m,s,t,i,j:longint;
function max(a,b,c:longint):longint;
  var
    k:longint;
  begin
    if a>b then k:=a else k:=b;
    if k<c then k:=c;
    max:=k;
  end;
begin
  assign(input,'escape.in');
  assign(output,'escape.out');
  reset(input);
  rewrite(output);
  readln(m,s,t);
  for i:=0 to 10000 do
    begin
      a:=0;
      b:=0;
    end;
  for i:=1 to t do
    begin
      for j:=0 to 9 do
        begin
          b[j]:=max(a[j]+17,a[j+4],0);
          if b[j]>=s then
            begin
              writeln('Yes');
              writeln(i);
              close(input);
              close(output);
              halt;
            end;
        end;
      for j:=10 to m do
        begin
          b[j]:=max(a[j]+17,a[j+4],a[j-10]+60);
          if b[j]>=s then
            begin
              writeln('Yes');
              writeln(i);
              close(input);
              close(output);
              halt;
            end;
        end;
      a:=b;
    end;
  writeln('No');
  writeln(a[m]);
  close(input);
  close(output);
end.

得了80分
离线orangeclk
只看该作者 3 发表于: 2007-11-18
这题是从别处抄的,强烈鄙视!
RP降至零点,NOIP2007完美彻底挂掉。。。
离线hzxiong
只看该作者 4 发表于: 2007-11-21
     
离线steven
只看该作者 5 发表于: 2007-11-21
Program escape;
var
        m,s,t,mn,sn,tn:longint;
        p:boolean;
begin
        Assign(input,'escape.in');
        reset(input);
        readln(m,s,t);
        close(input);
        Assign(output,'escape.out');
        rewrite(output);
        if s<=17 then begin writeln('Yes');writeln(1);close(output);halt;end;
        while (sn<s) and (tn<t) and (m>=10) do
              begin
              sn:=sn+60;
              tn:=tn+1;
              m:=m-10;
              end;
        while (sn<s) and (tn<t) do
              begin
              p:=false;
              case m of
                  0:if ((t-tn)>=7) and (s-sn>119) then begin tn:=tn+7;sn:=sn+120;p:=true;end;
                  1:if ((t-tn)>=7) and (s-sn>119) then begin tn:=tn+7;sn:=sn+120;p:=true;end;
                  2:if ((t-tn)>=3) and (s-sn>51) then begin tn:=tn+3;sn:=sn+60;m:=0;p:=true;end;
                  3:if ((t-tn)>=3) and (s-sn>51) then begin tn:=tn+3;sn:=sn+60;m:=1;p:=true;end;
                  4:if ((t-tn)>=3) and (s-sn>51) then begin tn:=tn+3;sn:=sn+60;m:=2;p:=true;end;
                  5:if ((t-tn)>=3) and (s-sn>51) then begin tn:=tn+3;sn:=sn+60;m:=3;p:=true;end;
                  6:if ((t-tn)>=2) and (s-sn>34) then begin tn:=tn+2;sn:=sn+60;m:=0;p:=true;end;
                  7:if ((t-tn)>=2) and (s-sn>34) then begin tn:=tn+2;sn:=sn+60;m:=1;p:=true;end;
                  8:if ((t-tn)>=2) and (s-sn>34) then begin tn:=tn+2;sn:=sn+60;m:=2;p:=true;end;
                  9:if ((t-tn)>=2) and (s-sn>34) then begin tn:=tn+2;sn:=sn+60;m:=3;p:=true;end;
                  end;
              if not p then begin tn:=tn+1;sn:=sn+17;end;
              end;
        if (sn>=s) and (tn<=t) then begin Writeln('Yes');Writeln(tn);end
                              else begin Writeln('No');Writeln(sn);end;
        close(output);
end.
离线steven
只看该作者 6 发表于: 2007-11-21
这题是贪心,我和同学讨论过,觉得这样应该没什么太大问题,不过没怎么测试,只有理论依据,请大家出几个测试点多测一下
离线steven
只看该作者 7 发表于: 2007-11-21
好消息,本人刚才测了一下(本网有数据),全对
离线独孤幽梦
只看该作者 8 发表于: 2007-11-23
其实这道题用贪心即可全过,上面那种解法实在是有点无语。在此说一下我的穷+贪算法。(我这道题全过了,最大的数据测试测试时也只是一闪而过)
离线独孤幽梦
只看该作者 9 发表于: 2007-11-23
首先分析一下总路程应是如何得到的:
    s=mtime*60+zoutime*17
因为用魔法永远比跑步的信价比高,所以贪心策略应是只要能用魔法,就坚决要用,可得如下推倒。
        mtime=(mochuzhi+xiutime)div 10
        mtime+xiutime+zoutime=zongtime
根据以上推倒,我们只需用一个xiushi便可表示出所有未知数。
因此,此题的关键思路已经诞生,便是穷举xiutime的值。
再看一下数据T<=300000 。
因为除循环以外,循环内只是一些简单的赋值语句和if语句,速度应该是很快的。
再循环中用一个max 记录在xiutime取不同值时所能走到的最大路程
做到这, 已经基本解决了,No是直接输出max
Yes时,作如下处理
先消步行的时间和路程
再消魔法所需的时间和路程(贪心)
最后输出所需的最少时间
快速回复
限100 字节
 
上一个 下一个