宁波住房和建设局网站首页,软件开发哪家公司好,彩神app官方网站开发,公司企业网站设计尺寸题目描述 有一条河#xff0c;左边一个石墩(A区)上有编号为1#xff0c;2#xff0c;3#xff0c;4#xff0c;…#xff0c;n的n只青蛙#xff0c;河中有k个荷叶(C区)#xff0c;还有h个石墩(D区)#xff0c;右边有一个石墩(B区)#xff0c;如下图2—5所示。n只青蛙…题目描述 有一条河左边一个石墩(A区)上有编号为1234…n的n只青蛙河中有k个荷叶(C区)还有h个石墩(D区)右边有一个石墩(B区)如下图2—5所示。n只青蛙要过河(从左岸石墩A到右岸石墩B)规则为 (1)石墩上可以承受任意多只青蛙荷叶只能承受一只青蛙(不论大小) (2)青蛙可以A→B(表示可以从A跳到B下同)A→CA→DC→BD→BD→CC→D (3)当一个石墩上有多只青蛙时则上面的青蛙只能跳到比它大1号的青蛙上面。 你的任务是对于给出的hk计算并输出最多能有多少只青蛙可以根据以上规则顺利过河? 输入 一行两个整数h和k分别表示k片荷叶和h个石墩 输出 输出最多能有多少只青蛙可以根据以上规则顺利过河 样例输入 2 3样例输出 16 思路递推dp 首先青蛙只能往前跳不能往后跳而且只能12345这样排下去所以要想使最多的青蛙到达对岸只需使编号最大的青蛙首先跳到对岸否则编号更大的青蛙就跳不过去了。 然后要想使编号最大的青蛙首先跳到对岸只需让河面上承载最多的青蛙。而荷叶上只能承载一只青蛙所以需要让青蛙尽可能多地叠到石墩上。 接下来便是核心内容(f[i]表示当有k个荷叶i个石墩时过河青蛙的最大数量) 1、若有k个荷叶没有石墩则最多有k1个青蛙。所以f[0]k1不需要解释了吧 2、若有k个荷叶1个石墩则只需要使石墩上承载最多的青蛙。进一步分析我们只需要将石墩当做对岸这样就变成1的情况了。所以f[1]f[0]k1 3、若有k个荷叶2个石墩则需要先让石墩1作为对岸叠完后再让石墩2作为对岸。所以f[2]f[1]f[0]k1 继续往下推理得到状态转移方程f[h]f[0]f[1]f[2]……f[h-1]k1; 代码 1 #include iostream2 #include bits/stdc.h3 using namespace std;4 int n,m,sum;5 int a[10000];6 int main()7 {8 scanf(%d%d,n,m);9 a[0]m1;
10 suma[0];
11 for(int i1;in;i)
12 {
13 a[i]sum;
14 suma[i];
15 }
16 cout sum endl;
17 return 0;
18 } View Code 转载于:https://www.cnblogs.com/SoulSecret/p/8447457.html
