递归与递推 - 青蛙过河

青蛙过河

时间限制: 1 Sec   内存限制: 128 MB

题目描述

一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，…，n编号。规定初始时这队青蛙只能趴在左岸的石头L上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下，且编号相邻。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。

输入

s和y，分别表示溪中有S根石柱和y片荷叶

输出

最多能跳过多少只青蛙

样例输入

0 1

样例输出

2

分析思路：

#include <stdio.h>
long long river[100];
int main()
{
    int i,s,y;
    scanf("%d%d",&s,&y);
    river[0]=y+1;
    for(i=1;i<=s;i++)
        river[i]=2*river[i-1];
    printf("%lld\n",river[s]);
    return 0;
}

解法原地址：http://www.docin.com/p-1440231309.html