nbhkdz.com冰点文库

NOIP2005提高组复赛第二题


过河 【问题描述】在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上 有一些石子, 青蛙很讨厌踩在这些石子上。 由于桥的长度和青蛙一次跳过的距离都是正整数, 我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中 L 是 桥的长度) 。坐标为 0 的点表示桥的起点,坐标为 L 的点表示桥的终点。青蛙从桥的起点开 始,不停的向终点方向跳跃。

一次跳跃的距离是 S 到 T 之间的任意正整数(包括 S,T) 。当 青蛙跳到或跳过坐标为 L 的点时,就算青蛙已经跳出了独木桥。 题目给出独木桥的长度 L,青蛙跳跃的距离范围 S,T,桥上石子的位置。你的任务是确定青 蛙要想过河,最少需要踩到的石子数。 【输入文件】输入文件 river.in 的第一行有一个正整数 L(1 ≤ L ≤ 109) ,表示独木桥 的长度。第二行有三个正整数 S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离, 及桥上石子的个数,其中 1≤S≤T≤10,1≤M≤ 100。第三行有 M 个不同的正整数分别表示这 M 个石子在数轴上的位置(数据保证桥的起点和终点处没有石子) 。所有相邻的整数之间用 一个空格隔开。 【输出文件】输出文件 river.out 只包括一个整数,表示青蛙过河最少需要踩到的石子数。 方法 1:搜索 ?直叙式搜索不行:搜索桥有困难(桥的长度 1..109) ;搜索石子更困难,(石头的分布是没有 任何规律) ?优化:以桥的长度为对象搜索+巧妙的剪枝 ?分析:从桥的一侧到另一侧,中间最多只有 100 个石子。假设桥长为最大值(109),石头数 也为最大值(100), 则中间一定会有很多“空长条” (两个石子中的空地), 关键是如何在处理时 把这些“空长条”跳过,使得运算次数降到 M 次。 先求出青蛙可能跳到的所有位置,然后就可以在忽略“空长条”的前提下,计算青蛙过河最少 需要踩到的石子数了。算法的时间复杂度为 O(m2) 方法 2、动态规划 设 opt[n]为青蛙到达 n 位置最少需要踩到的石子数。 rock[n]= 这个方程的时间复杂度是 O(n)级的 ,显然在竞赛时限内, n≤109 的极限数据是无法出

?1 ? ? ?0 ?

n位置有石子 n位置无石子

opt[ n] ? min {opt[ n ? i ] ? rock[ n]}
S ? i ?T
解的 优化方法:压缩法 ?结论: ?若(采用跳跃距离 p 和 p+1 时可以跳至任何位置 Q) ,则在 Q≥P*(P-1)时是一定有解的。

px ? ( p ? 1) y ? Q
为什么呢? Because 证明

?由于 p 与 p+1 间隔 1,故方程 px+(p+1)y=Q 有整数解,设其解为 ? x=x0+(p+1)t,y=y0-pt(t 是整数) ?取适当的 t,使得 0≤x≤p(只需在 x0 上加上或减去若干个 p+1),则当 Q>p(p-1)-1 时,有 ?(p+1)y=Q-px>p(p-1)-1-px≥p(p-1)-1-p*p=-(p+1) ?于是 y>-1,故 y≥0 也是非负整数。证毕. 由于题目给出的一个区间是 1≤S≤T≤10,于是当相邻的两个石子之间的距离不小于 8*9=72 时,则后面的距离都可以到达,我们就可以认为它们之间的距离就是 72。如此一来,我们 就将原题 L 的范围缩小为了 100*72=7200,动态规划算法完全可以承受了。但是当 S=T 时, 上述等式是无法使用的,在这种情况下,只需要在所有石子中,统计出坐标是 S 倍数的石 子个数就可以了。 设 n 为桥上的石子数(1≤n≤m) ; b[i]为能否用 s 到 t 的一次跳跃距离跳至 i 远的标志 b[i]=true i=0 b[i]= 1≤i≤90 c[v]为青蛙能否跳到相对距离为 v 远的标志(v≤90) ? ? c[v]= a[i,j]为青蛙跳至 x[i]左方相对距离为 j 的位置时所经过的最少石子总数。 j=0, 若 说明青蛙踩

? false ? ? true ? b[v ] ?

v?0 v ? s ( s ? 1) 0 ? v ? s ( s ? 1)

到了桥上的第 i 个石子。初始时,a[i,j]=n+1(0≤i≤n,0≤j≤t-1) 。 第 1 种情况:x[i]-j 位置位于 x[i-1]的左方,即 x[i]-j≤x[i-1]

显然,跳至 x[i]-j 位置经过的最少石子总数为 a[i-1,j-x[i]+x[i-1]]

第 2 种情况:x[i]-j 位置位于 x[i-1]的右方,即 x[i]-j>x[i-1]

显然,如果青蛙能够由 x[i-1]-v 位置跳至 x[i]-j 位置(can(x[i]-j-x[i-1]+v)=true) ,则跳至 x[i]-j 位置经过的石子总数为 a[i-1,v]或者为 a[i-1,v]+1(j=0 时,即踩到了桥上的第 i 个石子) 。但 究竟 v 多大时,才能使得最少石子数最少呢,我们无法预知,只能在 0‥t-1 的范围内一一 枚举 v,从中找出经过的最少石子数。 a[i,j]=

? a[i ? 1, j ? x[i ] ? x[i ? 1]] ? ? ? 0min?1{a[i ? 1, v] can[ x[i ] ? j ? x[i ? 1] ? v]} ? v ?t ? min {a[i ? 1, v] can[ x[i ] ? j ? x[i ? 1] ? v]} ? 1 ?0?v?t ?1 ?

x[i ] ? j ? x[i ? 1] x[i ] ? j ? x[i ? 1], j ? 0 x[i ] ? j ? x[i ? 1], j ? 0

最后,我们枚举青蛙跳出独木桥前的最后一个起跳位置 x[n]-i(0≤i≤t-1) ,从中计算出青蛙 过河最少需要踩到的石子数

0?i ?t ?1

min {a[n, i ]}

?var L,s,t,m,n,i,j,v,best:longint; ? x:array [0..100] of longint;{由左而右记录每个石子的位置} ? a:array [0..100,0..9] of longint;{a[i,j]为青蛙跳到 x[i]-j 位置经过的最少石子数} ? b:array [-10..90] of boolean;{b[i]记录能否用 s 到 t 这 t-s+1 种距离从原点到达横坐标为 i 的位置} ? function can(v:longint):boolean;{判别青蛙能否跳到位置 v} ? begin ? if v<0 ? then can:=false ? else if v>=s*s-s{可以证明,当 v≥s(s-1)时,一定可以用 s 和 s+1 两种跳跃距离到达位置 v, 所以要对 s=t 作特殊处理} ? then can:=true ? else can:=b[v] ? end;{can} ?begin ? assign(input,'river.in');reset(input);{输入文件读准备} ? readln(L);readln(s,t,m);{读独木桥长度、青蛙一次跳跃的最小距离,最大距离和桥上的石 子数} ? for i:=1 to m do read(x[i]);{输入每个石子在数轴上的位置} ? readln; close(input);{关闭输入文件} ? for i:=1 to m-1 do{按照由左而右的顺序排列石子} ? for j:=1 to m-1 do ? if x[j]>x[j+1] then begin v:=x[j];x[j]:=x[j+1];x[j+1]:=v end;{ then } ?n:=m;while x[n]>L do dec(n);{去除独木桥外的石子} ? if s=t{若青蛙每次跳跃的距离唯一, 则青蛙过河最少需要踩到的石子数 best 即为坐标位置 为 s 整倍数的石子数} ? then begin ? best:=0; ? for i:=1 to n do if x[i] mod s=0 then inc(best); ? assign(output,'river.out');rewrite(output);{输出文件写准备} ? writeln(best); {输出 best 后关闭输出文件并成功退出} ? close(output); halt

? end;{ then } ? fillchar(b,sizeof(b),false); ? b[0]:=true;{计算小范围的情况} ? for i:=1 to 90 do{递推每一个坐标位置} ?for j:=s to t do {枚举青蛙一次跳跃的可能距离,计算青蛙能否跳到坐标位置 i} ?b[i]:=b[i] or b[i-j]; ? for i:=0 to n do{状态转移方程初始化} ? for j:=0 to t-1 do a[i,j]:=n+1; ? x[0]:=0;{在 0 位置处增加一个虚拟的石子} ? a[0,0]:=0;{ 青蛙在 0 位置起跳} ?for i:=1 to n do{递推桥上的每一个石子} ? for j:=0 to t-1 do{枚举每一个可能的跳前位置} ? if x[i]-j<=x[i-1]{如果 x[i]-j 位置位于石子 i-1 的左端} ? then a[i,j]:=a[i-1,j-x[i]+x[i-1]] ? else begin{若 x[i]-j 位置位于石子 i-1 的右端,则枚举每一个可能的跳前} ? for v:=0 to t-1 do ? if can(x[i]-j-x[i-1]+v) and (a[i-1,v]<a[i,j]) {若青蛙可以从 x[i-1]-v 跳到 x[i]-j 位 置,且跳到 x[i-1]-v 位置经过的最少石子数为目前最少,则取跳到 x[i-1]-v 位置经过的最少 石子数} ? then a[i,j]:=a[i-1,v]; ? if j=0 then inc(a[i,j]){若踩到第 I 个石子,则经过的石子数+1} ? end;{ else } ? best:=n+1; ? for i:=0 to t-1 do{枚举青蛙跳出独木桥前的最后一个起跳位置,计算经过的石子数,从中 找出最优解} ? if a[n,i]<best then best:=a[n,i]; ? assign(output,'river.out');rewrite(output);{输出文件写准备} ? writeln(best);{输出最优解} ? close(output){关闭输出文件} ?end.


NOIP2005提高组复赛第二题_过河分析

【输入文件】输入文件 river.in 的第一行有一个正整数 L(1 ≤ L ≤ 109) ,表示独木桥 的长度。第二行有三个正整数 S,T,M,分别表示青蛙一次跳跃的最小...

NOIP2005提高组复赛试题

◆公告◆NOIP2005 复赛提高组试题 公告◆第十一届全国青少年奥林匹克信息学联赛复赛提高组试题 (提高组 三小时完成) http://www.oifans.cn/ 谁拿了最多奖学金...

NOIP2005提高组初赛试题及答案

NOIP2005提高组初赛试题及答案_财会/金融考试_资格考试/认证_教育专区。第十一届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组pascal 语言二小时完成)●● 全部...

NOIP2005提高组解题报告

算法分析: 从第一个人处断开,将圆环的问题转化为序列的问题。如果可以, 求出...等价表达式_NOIP2005提高... 6页 2下载券 NOIP2009提高组复赛题解 12页 1下载...

NOIP2005普及组复赛试题(附题解)

第二行只包括一个 100 到 120 之间 (包含 100 和 120) 的整数 (以 厘米...NOIP2005提高组复赛试题 8页 免费 NOIP2005普及组复赛试题 8页 免费 NOIP2005...

NOIP2005提高组解题报告

解题报告并非源程,这样更有助于思维的锻炼,第一题中的一些代码均是在 Word ...NOIP2005提高组复赛第二... 5页 1下载券 NOIP2005提高组解题报告 3页 1下载...

历届noip提高组复赛试题

历届noip提高组复赛试题_学科竞赛_高中教育_教育专区...B+B (即全部由 B 产生) 第二届全国青少年信息学...2005 年 第十二届全国青少年信息学奥林匹克 联赛复赛...

NOIP历年复赛提高组试题(2004-2013)

【输入文件】 输入文件 chorus.in 的第一行是一个整数 N(2<=N<=100), ...(NOIP2005)复赛试题(提高组 竞赛用时:3 小时) 1、谁拿了最多奖学金(...

NOIP历年复赛提高组试题(2006-2014)

) 2 2006~2014 年 NOIP 复赛试题集(提高组) 从第 2 行到第 m+1 行,第...(提高组) hotel.in 523 05 13 02 14 15 【输入输出样例说明】 客栈编号 ...

2009noip提高组复赛题解

2009noip提高组复赛题解_企业管理_经管营销_专业资料。NOIP2009 提高組複賽試題解題報告 NOIP2009 提高組複賽試題解題報告 一、潛伏者(spy) 問題描述: 給出密文及...