P1244 青蛙过河

洛谷 P1244 青蛙过河

链接

https://www.luogu.org/problem/P1244

题目

题目描述

有一条河,左边一个石墩(A区)上有编号为1,2,3,4,…,n的n只青蛙,河中有k个荷叶(C区),还有h个石墩(D区),右边有一个石墩(B区),如下图所示。n只青蛙要过河(从左岸石墩A到右岸石墩B),规则为:

img

(1)石墩上可以承受任意多只青蛙,荷叶只能承受一只青蛙(不论大小);

(2)青蛙可以:A→B(表示可以从A跳到B,下同),A→C,A→D,C→B,D→B,D→C,C→D;

(3)当一个石墩上有多只青蛙时,则上面的青蛙只能跳到比它大1号的青蛙上面。

你的任务是对于给出的h,k,计算并输出最多能有多少只青蛙可以根据以上规则顺利过河?

输入格式

两个整数h,k

输出格式

一个整数,表示最多能有多少只青蛙可以根据以上规则顺利过河。

输入输出样例

输入 #1

1
2 3

输出 #1

1
16

思路

这道题超出了我的想象。。。。。我没怎么看懂,之后看了别人的博客才搞明白,按道理说用动态规划,但是化简之后的式子就是直接h,k组成的,如果没有石墩,那么只有k+1个,每有一个石墩,数量就增加为(k+1)*2^h,就是每多一个石墩就多了一次周转的机会,然后输出结果就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>

using namespace std;

int main()
{
int h,k;
cin>>h>>k;
long long num=k+1;
for(int i=0;i<h;i++)
{
num=num*2;
}
cout<<num;

return 0;
}
---本文结束,感谢阅读---