青蛙过河

http://www.nowcoder.com/questionTerminal/f6150d05ec444aaea74641426fbdb756

设 $A(n, m)$ 是能过河的青蛙的数量， $n$ 为石墩的数量， $m$ 为荷叶的数量。
则 $A(0, m) = m+1$ 。这是比较显然的，让青蛙在每个荷叶上一只，再让一只跳到对面，荷叶上的青蛙然后跳到对面。
对于 $A(n, m)$ , 我们先河对岸的落脚点，将一个河墩视为对岸，则，最多能跳 $A(n-1, m)$ 个青蛙过去。此时还剩下 $n-2$ 个河墩，如法炮制，会有 $A(n,m) = \Sigma_{i=0}^{n-1}A(i, m) + A(0, m)$
为什么会多一个 $A(0, m)$ 呢，因为当所有石墩都占满了青蛙后，我们就可以选择跳对岸了。

解得 $A(n, m) = (m+1)2^{n}$

这题我没想出来，感谢楼上大佬的思路

int main(){
    int n, m; cin >> n >> m;
    cout << (m+1)*(1<<n) << endl;

    return 0;
}

全部评论

推荐最新楼层

11-18 15:50

牛客运营

巨坑。。。一定别去这些假国企

国务院国有资产监督管理委员会曾发布过《假冒中央企业名单》的公告，列举出一系列打着国企的旗号，但实际上并不具备国企的资质和背景，甚至存在欺诈风险。为了避免牛友们上当受骗，牛牛整理了部分清单：中自基业控股集团有限公司中自云智慧城市科技集团有限公司中企万邦（北京）企业管理咨询有限公司江西冀睿能源产业有限公司中盛航信（深圳）技术有限公司通航博金建设发展（成都）集团有限公司国华永瑞（杭州）产业管理有限公司商投能运（海南）投资有限公司南昌金赞科技有限公司中金文华（山东）实业有限公司华金产业发展（海南）有限公司国金南瑞（天津）建设集团有限公司……同时，我们在求职央国企的时候也要注意招聘企业、招聘信息的真实性...

点赞评论收藏

11-18 23:23

中国药科大学外贸业务员

哈哈，终于接到offer了！

这次是来自一家世界500强的外企，真是让我感到无比幸福！找工作真的是靠运气和机遇，面试过程轻松，薪资也很满意。现在终于迎来了转机，心里真是美滋滋的！希望未来的工作能更加顺利！

牛客创作赏金赛

点赞评论收藏

11-11 15:12

南昌大学材料工程师

完辣

211硕双非本，原来这么垃圾？投一次被拒一次，笑死。 #0offer是寒冬太冷还是我太菜#

一个菜鸡罢了：哥们，感觉你的简历还是有点问题的，我提几点建议，看看能不能提供一点帮助 1. ”新余学院“别加粗，课程不清楚是否有必要写，感觉版面不如拿来写一下做过的事情，教育经历是你的弱势就尽量少写 2. “干部及社团经历”和“自我评价”删掉 3. 论文后面的“录用”和“小修”啥的都删掉，默认全录用，问了再说，反正小修毕业前肯定能发出来 4. 工作经验和研究成果没有体现你的个人贡献，着重包装一下个人贡献

0offer是寒冬太冷还是我太菜

点赞评论收藏