蜜蜂路线
题目背景
无
题目描述
一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房 $m$ 开始爬到蜂房 $n$,$m<n$,有多少种爬行路线?(备注:题面有误,右上角应为 $n-1$)
输入格式
输入 $m,n$ 的值
输出格式
爬行有多少种路线
样例 #1
样例输入 #1
1 14
样例输出 #1
377
提示
对于100%的数据,$1 \le M,N\le 1000$
题解:
思路:和P1255数楼梯几乎是一样的,都是高精度+斐波那契数列。从m爬到n,其实就相当于从1 爬到n - m + 1,因为算法的斐波那契数列是从0开始,即fib[0] = 1, fib[1] = 1,所以只需要输出fib[n - m]就行了
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int fib[N][N];
int len = 1;
void hpa(int k)
{
for (int i = 1; i <= len; i++)
{
fib[k][i] = fib[k - 1][i] + fib[k - 2][i];
}
for (int i = 1; i <= len; i++)
{
if (fib[k][i] >= 10)
{
fib[k][i + 1] += fib[k][i] / 10;
fib[k][i] %= 10;
if (fib[k][len + 1] > 0) len++;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int m, n;
cin >> m >> n;
fib[1][1] = 1, fib[2][1] = 2;
for (int i = 3; i <= n - m; i++)
{
hpa(i);
}
for (int i = len; i >= 1; i--) cout << fib[n - m][i];
return 0;
}
斐波那契+高精度有点看不懂,题主可以解答一下嘛,我也是从洛谷刷题过来的,但是 洛谷的题解有点看不懂高精度