各位朋友请帮我以下了啊 再不帮我 我就死定了
E. 青蛙过河(Frog)
大小各不相同的一队青蛙站在河左岸的石墩（记为A）上，要过到对岸的石墩(记为D)上去。河心有几片菏叶(分别记为Y1…Ym)和几个石墩(分别记为S1…Sn)。图示如下：

左岸石墩A

右岸石墩D

荷叶Yi

河心石墩Sj

青蛙的站队和移动方法规则如下：

1． 每只青蛙只能站在荷叶、石墩，或者仅比它大一号的青蛙背上（统称为合法的落脚点）；

2． 一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点；

3． 青蛙允许从左岸A直接跳到河心的石墩、荷叶和右岸的石墩D上，允许从河心的石墩和荷叶跳到右岸的石墩D上；

4． 青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动；

5． 青蛙在离开左岸石墩后，不能再返回左岸；到达右岸后，不能再跳回；

6． 假定石墩承重能力很大，允许无论多少只青蛙都可呆在上面。但是，由于石墩的面积不大，至多只能有一只青蛙直接站在上面，而其他的青蛙只能依规则1落在比它大一号的青蛙的背上。

7． 荷叶不仅面积不大，而且负重能力也有限，至多只能有一只青蛙站在上面。

8． 每一步只能移动一只青蛙，并且移动后需要满足站队规则；

9． 在一开始的时候，青蛙均站在A上，最大的一只青蛙直接站在石墩上，而其它的青蛙依规则6站在比其大一号的青蛙的背上。

青蛙希望最终能够全部移动到D上，并完成站队。

设河心有m片荷叶和n个石墩，请求出这队青蛙至多有多少只，在满足站队和移动规则的前提下，能从A过到D。

例如，在m=1且 n=1时，河心有一片荷叶（Y1）和一个石墩（S1），此时至多有4只青蛙能够过河（由小到大称为1、2、3、4），过河的一种方法为：

开始

1

2

3

4

A S1 Y1 D

Step 1
1 from A to Y1
2

3

4 1

A S1 Y1 D

Step 2
2 from A to S1
3

4 2 1

A S1 Y1 D

Step 3
1 from Y1 to S1
3 1

4 2

A S1 Y1 D

Step 4
3 from A to Y1
1

4 2 3

A S1 Y1 D

Step 5
4 from A to D
1

2 3 4

A S1 Y1 D

Step 6
3 from Y1 to D
1 3

2 4

A S1 Y1 D

Step 7
1 from S1 to Y1
3

2 1 4

A S1 Y1 D

Step 8
2 from S1 to D
2

3

1 4

A S1 Y1 D

Step 9
1 from Y1 to D
1

2

3

4

A S1 Y1 D

此例中，当河心有一片荷叶和一个石墩时，4只青蛙能够跳动9步过河。

[输入文件]

文件仅有两行，每一行仅包含一个整数和一个换行/回车符。第一行的数字为河心的石墩数n（0<=n<=25），第二行为荷叶数m（0<=m<=25）。

[输出文件]

文件中仅包含一个数字和一个换行/回车符。该数字为在河心有n个石墩和m片荷叶时，最多能够过河的青蛙的只数。

[输入输出文件样例]

Input.txt

1

1

Output.txt

4

这道题我做过，帮您搜了下，自己去看看，汗，当时我写了Ｎ个程序．．．．．
http://www.bc-cn.net/bbs/dispbbs.asp?boardid=5&replyid=125005&id=61745&page=1&skin=0&Star=1

题目不一样啊！！

我昨天晚上把这个问题下了，看了下，不知道这个想法是不是对的：（因为我现在还无法证明这是最多的）
假设有n个石墩，m片荷叶，最多能容纳的青蛙有个公式：(n+2m)(n+1)/2+1;
reason as follows:
首先Ａ的青蛙分别往每片荷叶上跳，然后依次往石墩上（Ｄ不算）跳，等石墩满后，那只跳到最后一个石墩的青蛙不动，把其他青蛙，按站队原则依次跳到那个石墩上。于是，那个石墩共站了n+m只青蛙，其他的依此类推，第二个石墩能站n+m-1只青蛙，第三个石墩能站n+m-2只青蛙，．．．，第n个石墩能站m+1只青蛙，剩下的m片荷叶分别站一只青蛙，这样石墩和荷叶全部站满，最多Ａ石墩再剩一只青蛙，才能满足要求，不然最下面的那只青蛙将跳不出去．所以，总共有n+m,n+m-1,n+m-2,...,m+1,m,1的和个。加起来正好是上面的那个式子．

不知道是否分析错误了，大家帮忙看看。

楼上的青蛙不是最多的,我有个思路,大家来看看:
没有用任何语言编写，是纯数学推导。
设n为石墩数,m为荷叶数 ,设F[n,m]表示当有n个石墩,m个荷叶时,能跳过去的最多青蛙数，我们现在可以增加一个石墩，此时就有n+1个石墩了,把第n+1个石墩看成右岸,这样就可以把F[n,m]个青蛙从左岸跳到第n+1个石墩上(借助原来河里的n个石墩,m个荷叶), 这时第n+1个石墩上就有F[n,m]个青蛙了，此时河里还有n个空石墩,m个空荷叶,还可以帮助F[n,m]个青蛙从左岸跳到真正的右岸,此时再把第n+1个石墩看成左岸, 借助河里的n个石墩,m个荷叶,顺利的跳到右岸青蛙的身上.至此一共可以跳过去 2*F[n,m]个青蛙.
由此可知： 关系式 F[n+1，m]=2*F[n，m]

推导: F[n，m]=2*F[n-1，m]
=4*F[n-2，m]
……
=(2^i)*F[n-i，m]
……
=(2^n)*F[0，m]
当n=0时,河里只有m个荷叶,每个叶上只能有一个青蛙,再加上从右岸可以直接跳到左岸的一只,所以共有m+1个青蛙,即F[0,m]=m+1;所以
F[n，m]=(m+1）*2^n

其实此题就是Hanoi(汉诺塔)的改进版,把荷叶看成一个整体，不要被题目的形式所迷惑!

[此贴子已经被作者于2006-8-22 22:29:49编辑过]

佩服楼上的精彩推断。
我也想过用动态规划的方法来解决这个问题，但在降低石墩数目的方案中始终没想出来。所以取巧猜了上面的错误想法。
哈哈，您所说没错，这就是ＨＡＮＯＩ的另一版本，见笑了。