a081. NOI2000 Day2.2.青蛙过河
內容 ：
大小各不相同的一队青蛙站在河左岸的石墩（记为A）上，要过到对岸的石墩(记为D)上去。河心有几片菏叶(分别记为Y1…Ym)和几个石墩(分别记为S1…Sn)。
图示如下 
青蛙的站队和移动方法规则如下：
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），过河的一种方法为：
| 开始 | 1234A S1 Y1 D | |
| Step 1 | 1 from A to Y1 | 234 1A S1 Y1 D |
| Step 2 | 2 from A to S1 | 34 2 1A S1 Y1 D |
| Step 3 | 1 from Y1 to S1 | 3 14 2A S1 Y1 D |
| Step 4 | 3 from A to Y1 | 14 2 3A S1 Y1 D |
| Step 5 | 4 from A to D | 1 2 3 4A S1 Y1 D |
| Step 6 | 3 from Y1 to D | 1 3 2 4A S1 Y1 D |
| Step 7 | 1 from S1 to Y1 | 3 2 1 4A S1 Y1 D |
| Step 8 | 2 from S1 to D | 23 1 4A S1 Y1 D |
| Step 9 | 1 from Y1 to D | 1 2 3 4A S1 Y1 D |
此例中，当河心有一片荷叶和一个石墩时，4只青蛙能够跳动9步过河。
輸入說明
：
文件仅有两行，每一行仅包含一个整数和一个换行/回车符。第一行的数字为河心的石墩数n（0<=n<=25），第二行为荷叶数m（0<=m<=25）。
輸出說明
：
文件中仅包含一个数字和一个换行/回车符。该数字为在河心有n个石墩和m片荷叶时，最多能够过河的青蛙的只数。
範例輸入 ：
1 1
範例輸出 ：
4
提示
：
出處
：
/**********************************************************************************/
/* Problem: a081 "NOI2000 Day2.2.青蛙过河" from NOI2000 Day2 第二题 */
/* Language: C */
/* Result: AC (3ms, 266KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-15 16:11:15 */
/**********************************************************************************/
#include<stdio.h>
main() {
int n, m, s2[26] = {1};
for(n = 1; n < 26; n++) s2[n] = s2[n-1]*2;
while(scanf("%d %d", &n, &m) == 2) {
printf("%d", s2[n]*(m+1));
}
return 0;
}
/*
設s[i,j]表示i根柱子，j片荷葉的情況下最多能通過的青蛙數。
不難得出：s[i,j]=2s[i-1,j]
解釋：i-1根柱子時，設終點為t，則有s[i-1,j]個青蛙到達t，增加1根柱子t'，
則到達t'的青蛙個數也為s[i- 1,j]，再將t'作為起點，則t'上的青蛙全部可以轉移到t上。
邊界條件，s[0,j]=j+1
所以這道題的答案就是2n(m+1)。
*/