蜜蜂路线

题目描述

一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房 $m$ 开始爬到蜂房 $n$，$m<n$，有多少种爬行路线？（备注：题面有误，右上角应为 $n-1$）

输入格式

输入 $m,n$ 的值

输出格式

爬行有多少种路线

样例 #1

样例输入 #1

1 14

样例输出 #1

377

提示

对于100%的数据，$1 \le M,N\le 1000$

思路

f(x) = f(x - 1) + f(x - 2)
如果m == x或m + 1 == x，则f(x) = 1
数据过大，long long不够大，必须上高精度。

AC代码

#include <iostream>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 1005;

int n, m;
vector<int> mem[maxn];

vector<int> add(vector<int> v1, vector<int> v2) {
   
   
    vector<int> v3;
    vector<int>::iterator it1 = v1.begin();
    vector<int>::iterator it2 = v2.begin();
    for(; it1 != v1.end() && it2 != v2.end(); it1++, it2++) {
   
   
        int sum = *it1 + *it2;
        v3.push_back(sum);
    }
    for(; it1 != v1.end(); it1++) {
   
   
        v3.push_back(*it1);
    }
    for(; it2 != v2.end(); it2++) {
   
   
        v3.push_back(*it2);
    }
    vector<int>::iterator it3 = v3.begin();
    bool flg = false;
    for(; it3 != v3.end(); it3++) {
   
   
        if(*it3 > 9) {
   
   
            *it3 -= 10;
            if(it3 + 1 == v3.end()) {
   
   
                flg = true;
            } else {
   
   
                *(it3 + 1) += 1;
            }
        }
    }
    if(flg) {
   
   
        v3.push_back(1);
    }
    return v3;
}

void printv(vector<int> v) {
   
   
    vector<int>::reverse_iterator rit = v.rbegin();
    for(; rit != v.rend(); rit++) {
   
   
        cout << *rit;
    }
    cout << endl;
}

void f(int x) {
   
   
    if(!mem[x].empty()) {
   
   
        return;
    }
    if(m == x || m + 1 == x) {
   
   
        mem[x].push_back(1);
        return;
    }
    f(x - 1);
    f(x - 2);
    mem[x] = add(mem[x - 1], mem[x - 2]);
}

int main() {
   
   
    cin >> m >> n;
    f(n);
    printv(mem[n]);
    return 0;
}