Question

杭电acm2018题和代码在图中，结果是WA，麻烦哪位大大帮我看下错误在哪





Answer 1

你的思路明显是错的。。你把n = 2代进去，你得到 的是1？
而结果应该是3
第一年， 1 + 1 。。 大生小
第二年 , 1+ 1 + 1 . 大再生小，
这个是简单的动态规划算法，下面是推理过程，你按照递推公式写一下就可以了。
f(1) = 1 + 1 = 2
f(2) = 1 + 1 + 1 = 3
f(3) = 1 + 1 + 1 + 1 = 4
f(4) = 1 + 1 + 1 + 1 + 1 + 1 = 1 + 4 + 1
f(5) = 1 + 5 + (1 + 1) + 1
f(6) = 1 + 6 + ( 1 + 2) + ( 1 + 1 ) + 1
..。
f(n) = f(n-1) + 所有达到能生育的数量
所有达到能生育的数量 = 1 + n / 4
所以结果应该是
=======
f(n) = f(n-1) + 1 + n/4
-===========
f(0) = 1
f(1) = f(0) + 1 + 1/ 4 = 2
f(2) = f(1) + 1 + 2 / 4 = 3
f(3) = f(2) + 1 + 3 / 4 = 4
f(4) = f(3) + 1 + 4 / 4 = 6
....