【动态规划-递推】HDU 2044 一只小蜜蜂...
条评论有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中,蜂房的结构如下所示。
输入数据的第一行是一个整数N,表示测试实例的个数,然后是N 行数据,每行包含两个整数a和b(0<a<b<50)。
对于每个测试实例输出蜜蜂从蜂房a爬到蜂房b的可能路线数,每个实例的输出占一行。
思路
很简单的斐波那契额数列的变形,用f
数组来记录从开始到当前位置的可能路线数,求a到b的路线数就可以转化为求f[b-a]
, ,数据量为0到50,所以先打表存进f数组,因此从头至尾只打表进行计算,以后需要直接调用即可。
AC代码
1 |
|
- 本文链接:【动态规划-递推】HDU 2044 一只小蜜蜂...
- 发布时间:2019年01月20日 - 22:53:09
- 更新时间:2021年02月03日 - 6:56:56
- 版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!
分享