【洛谷 P2437】蜜蜂路线 题解(递归+记忆化搜索+高精度)

简介: 蜜蜂路线问题:蜜蜂从蜂房$m$到$n$($m<n$)按数字递增爬行。给定$m$和$n$,求路线数。示例:$m=1$,$n=14$,输出$377$。100%数据$1\leq m,n\leq1000$。使用斐波那契序列优化,高精度处理大数。代码实现斐波那契存储并动态规划求解。

蜜蜂路线

题目描述

一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房 $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;
}
目录
相关文章
|
监控 网络协议 安全
网络攻击的常见手段
网络攻击的常见手段
481 0
|
算法
二分查找及模板深度解析:right <= left 还是 right < left ? mid=left+(right-left)/2还是mid=left+(right-left +1 )/2 ?
二分查找及模板深度解析:right <= left 还是 right < left ? mid=left+(right-left)/2还是mid=left+(right-left +1 )/2 ?
200 0
|
9月前
|
存储 人工智能 运维
AI导购革命:揭秘主动式智能导购AI助手的构建之道
本文基于《主动式智能导购AI助手构建》解决方案的实际部署体验,从引导与文档帮助、解决方案原理与架构理解、百炼大模型及函数计算应用明晰度、生产环境步骤指导四个方面进行了详细评估。指出尽管该方案具有创新性和实用性,但在文档详尽性、技术细节解释及生产环境适应性等方面仍有待提升。通过进一步优化,可增强解决方案的可用性和用户满意度。
359 31
|
编译器 Android开发 开发者
Android经典实战之Kotlin 2.0 迁移指南:全方位优化与新特性解析
本文首发于公众号“AntDream”。Kotlin 2.0 已经到来,带来了 K2 编译器、多平台项目支持、智能转换等重大改进。本文提供全面迁移指南,涵盖编译器升级、多平台配置、Jetpack Compose 整合、性能优化等多个方面,帮助开发者顺利过渡到 Kotlin 2.0,开启高效开发新时代。
485 0
|
C++
【洛谷 P1601】A+B Problem(高精)题解(高精度+向量)
该问题要求解决高精度加法(正数)的A+B问题。给定两个不超过10^500的大整数a和b,程序需输出它们的和。样例输入包括两个整数,如1和1,输出为2;另一样例是1001和9099,输出为10100。解决方案通过模拟十进制加法实现,代码使用C++,将输入转换为字符数组,然后逐位相加并处理进位。最终结果反向输出。
250 0
【洛谷 P1002】[NOIP2002 普及组] 过河卒 题解(递归+记忆化搜索)
`NOIP2002`普及组的过河卒问题是一个棋盘路径计数挑战。卒从$(0,0)$出发到$(n,m)$,只能向下或向右移动,马在$(c1,c2)$固定,控制某些点。任务是计算不受马阻挡的路径数。输入是目标和马的位置,输出是路径总数。使用动态规划和记忆化搜索避免重复计算,样例输入$(6,6,3,3)$输出$6$。代码中定义了$f(x,y)$计算$(x,y)$处的路径数,利用边界条件和递推关系计算。
204 0
|
网络架构
Ensp DHCP 接口地址池(配置命令)
Ensp DHCP 接口地址池(配置命令)
443 1
余三码和8421码的关系以及使用场景
余三码与8421码是两种不同的二进制编码方式,常用于表示十进制数。余三码是8421码加上3形成的无权码,具有自补性和进位信号特点,适合错误检测,但求和需修正。8421码是恒权码,方便二进制与十进制转换,常用于数字显示、数据传输和精确十进制运算。在计算机领域,两者各有应用场景,如BCD码用于七段显示器和精确计算,余三码则用于错误检测和简化算术操作逻辑设计。
|
存储 缓存 算法
操作系统(15)-----I/O设备管理(万字总结~)(3)
操作系统(15)-----I/O设备管理(万字总结~)(3)
260 0
qt初入门0:结构体中QString用memset导致崩溃分析及QLatin1String简单查看源码
qt初入门0:结构体中QString用memset导致崩溃分析及QLatin1String简单查看源码
620 0