回 帖 发 新 帖 刷新版面

主题:有个问题请高手指点

步步高升(Step by Step)
——华南师大附中袁豪 2001分区联赛模拟赛 提高组第二题
【问题描述】
春节的时候TENSHI去逛花市。她来到一个卖盆竹的摊位,看到一盆叫做“步步高升”的盆竹。“步步高升,步步高升……”学习就是要一步一步来,不能急,要打好基础。在稳固的基础上才谈得上步步高升!TENSHI若有所思。她看到这盆东西好意头,于是想买下。谁知一问价钱,“不贵不贵,才2XXRMB。”TENSHI差点没昏倒,囊中羞涩嘛。但是TENSHI还是很想买下来,于是她就在一旁观察。观察了一段时间,她发现这个卖盆竹的人和别人杀价很有规律。设此人第i次报价为Wi元,那么他第i+1次报的价格为Wi-A或Wi -B。到了最后,TENSHI以Z元成交,高高兴兴的回家去了。

【任  务】 
求TENSHI把盆竹的价格由W1元杀到Z元的方法总数。

【输入格式】
从文件STEP.INP读入数据。文件第一行有两个正整数W1和Z。第二行有两个正整数A和B。它们满足条件:
    10 ≤ W1 ≤106,1 ≤ Z ≤ 106 ,Z < W1
    2 ≤ A  、B  ≤ 10000,A≠B
【输出格式】
直接把所求得的方法总数输出到文件STEP.OUT的第一行。文件只有一行(包括换行符)。注意:结果不超过MAXLONGINT

【样例一】
STEP.INP    STEP.OUT
256 885 9    3889832

【样例二】
STEP.INP    STEP.OUT
100 1013 23    0
[思路]

  f (小于0)=0
  
f (0)=1

f (n)=f (n-A)+f (n-B)
w1-z=wi

程序如下:
program Step_by_Step;
const
  size=15000;
var
  w,z,ans,a,b:longint;
  h:array[0..size] of longint;
  fname:string;
  procedure init;
  begin
    readln(fname);
    assign(input,fname);
    reset(input);
    readln(w,z);
    readln(a,b);
    close(input);
  end;
  procedure main;
  var i:longint;
  begin
    fillchar(h,sizeof(h),0);
    h[w mod size]:=1;
    for i:=w-1 downto z do
       h[i mod size]:=h[(i+a) mod size]+h[(i+b) mod size];
    ans:=h[z mod size];
  end;
  begin
    init;
    main;
    writeln(ans);
  end.
这个思路如何理解?

回复列表 (共2个回复)

沙发

啊~~~~~~~~~~~~~~偶晕`

板凳

楼上的什么意思,具体讲讲思路。先谢了!

我来回复

您尚未登录,请登录后再回复。点此登录或注册