noip2005复赛试题2

sandy_zc_1

青蛙过桥

有一个独木桥，长度L<=10^9，有一只青蛙想通过它过河。
但是桥上有石子（数量M<=100），青蛙不想踩上他们。
大家都知道青蛙走路是一跳一跳的，现在给出青蛙一次能跳跃的最远距离T和最近距离S，S<=T<=10，给出L、M的值和每个石子与桥头的距离（青蛙每次跳跃的距离都是整数，桥的长度和各石子与桥头的距离也是整数），求青蛙过桥踩到的石子的最小数量。



大家做做看吧。 [em13]

lights

最白痴的方法就是遍历每种情况然后计数。效率惨啊！
想到分析出可以调整T-S差距的必经点段，分解成几段遍历计数，效率会提高，可当不存在这种点段时，反而浪费了分析时间。

要么就只判断当前步会否导致下一步必碰石子，效率高却未必最优解。
又想上面算出结果对再检验能否减少碰石子的点，算法又??拢

求教正解!

sandy_zc_1

目前我的考虑是动态规划。
当然不能按照每一步划分阶段（会严重地溢出），我目前的方法是按照过去了多少个石子来划分阶段。

sandy_zc_1

大家不是要求探讨算法吗，都来做做吧。

sandy_zc_1

先给出去年noip2004的第三题，相对简单很多，使用动态规划

合唱队形

【问题描述】

    N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

    合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，  则他们的身高满足T1<…<Ti>Ti+1>…>TK(1<=I<=K)。

    你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入文件】

    输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第I个整数Ti(130<=Ti<=230)是第I位同学的身高(厘米)。

【输出文件】

    输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

jason_6260

我的天，头晕了，完全不懂

zlcnkkm

条件：青蛙一次能跳跃的最远距离T和最近距离S，S<=T<=10
假定：青蛙能跳跃的最远距离为10
设：青蛙每次都能以最远距离踊跃 AND 所有石子的直径都为1，那么：青蛙一次能跳过9个石子
因此：石子的最优排列为：
~ 011111111101111111110111111111 ~
当：桥有足够长度，那么：青蛙一定踩不到石子

条件：桥上有石子（数量M<=100）
假定：石子数量100
设：石子是最优排列，那么：100个石子需要青蛙跳 12(100/9=11.111111111111111)次
当：桥长 >= 120(12*10)，那么：桥有足够长度

条件：独木桥，长度L<=10^9
假定：桥长=1000000000(10^9)
因为：桥长 >= 120，那么：桥有足够长度 成立
因为：桥有足够长度，那么：青蛙一定踩不到石子 成立

因此：
当：所有假定条件成立，那么：青蛙过桥踩到的石子的最小数量为0


看不懂，乱说的 = =U

sandy_zc_1

zlcnkkm: Re:noip2005复赛试题2

条件：青蛙一次能跳跃的最远距离T和最近距离S，S<=T<=10
假定：青蛙能跳跃的最远距离为10
设：青蛙...

你可能是没有看懂题，没有什么石子直径之类的问题。

还是把官方描述帖上来吧。

青蛙过河
(river.pas/c/cpp)

【问题描述】

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：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只包括一个整数，表示青蛙过河最少需要踩到的石子数。


请仔细阅读以免误解 -_-||[em13]

sandy_zc_1

【样例输入】

10
2 3 5
2 3 5 6 7

【样例输出】

2

【数据规模】

对于30%的数据，L <= 10000；

对于全部的数据，L <= 109。

sandy_zc_1

那么没有人做出“合唱队形”这道题吗？这道题应该简单很多。