洛谷 P2437 蜜蜂路线

摘要:
P2437蜜蜂路线题目描述一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房M开始爬到蜂房N,M˂N,有多少种爬行路线?输入输出格式输入格式:输入M,N的值输出格式:爬行有多少种路线输入输出样例输入样例#1:复制114输出样例#1:复制377说明对于100%的数据,M,Nle1000M,N≤1000思路:斐波那契。

题目描述

一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房M开始爬到蜂房N,M<N,有多少种爬行路线?

洛谷 P2437 蜜蜂路线第1张

输入输出格式

输入格式:

输入M,N的值

输出格式:

爬行有多少种路线

输入输出样例

输入样例#1:复制
1 14
输出样例#1:复制
377

说明

对于100%的数据,M,Nle 1000M,N1000

思路:斐波那契。

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>
using namespacestd;
intn,m;
structnond{
    int num[50000];
}f[1010];
void jia(intpos){
    f[pos].num[0]=max(f[pos-1].num[0],f[pos-2].num[0]);
    for(int i=1;i<=f[pos].num[0];i++)
        f[pos].num[i]=f[pos-1].num[i]+f[pos-2].num[i];
    for(int i=1;i<=f[pos].num[0];i++)
        if(f[pos].num[i]>=10){
            if(i==f[pos].num[0])    f[pos].num[0]++;
            f[pos].num[i+1]+=1;
            f[pos].num[i]%=10;
        }
    for(;f[pos].num[0]>=1;f[pos].num[0]--)    if(f[pos].num[f[pos].num[0]])    break;
}
intmain(){
    scanf("%d%d",&m,&n);
    n-=m;
    if(n==0){ cout<<"0";return 0;}    
    f[1].num[1]=f[1].num[0]=f[0].num[0]=f[0].num[1]=1;
    for(int i=2;i<=n;i++)    jia(i);
    for(int i=f[n].num[0];i>=1;i--)    cout<<f[n].num[i];
}

免责声明:文章转载自《洛谷 P2437 蜜蜂路线》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇kuangbin专题 专题九 连通图 POJ 3694 Networkecharts柱状图多组数据配置下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

Java基础面试题(1)

个人总结,仅自己学习用。愿与大家一起分享!如有错误请指正。 一、String,StringBuffer, StringBuilder 的区别是什么?String为什么是不可变的? 答: 1、String是字符串常量,StringBuffer和StringBuilder都是字符串变量。后两者的字符内容可变,而前者创建后内容不可变。 2、String不可变是...

ESP32开发(2)esp32-cam采集图像

ESP32-CAM摄像头开发板 USB转串口下载器 杜邦连接线若干        注意:GPIO0连接GND(下拉)的作用是让ESP32-CAM进入下载启动模式,这个模式里,才能利用Arduino IDE给ESP32编程,否则IDE会报错,代码烧录完成后,我们需要断开GPIO0和GND的连接,让ESP32进入正常的内存启动模式。 配置ESP32环...

Oracle之物化视图

来源于:http://www.cnblogs.com/Ronger/archive/2012/03/28/2420962.html 近期根据项目业务需要对oracle的物化视图有所接触,在网上搜寻关于这方面的资料,便于提高,整理内容如下: 物化视图是一种特殊的物理表,“物化”(Materialized)视图是相对普通视图而言的。普通视图是虚拟表,应用的局限...

Kafka提交offset机制

在kafka的消费者中,有一个非常关键的机制,那就是offset机制。它使得Kafka在消费的过程中即使挂了或者引发再均衡问题重新分配Partation,当下次重新恢复消费时仍然可以知道从哪里开始消费。它好比看一本书中的书签标记,每次通过书签标记(offset)就能快速找到该从哪里开始看(消费)。 Kafka对于offset的处理有两种提交方式:(1) 自...

绘制echarts折线图

利用eclipse和MySQL数据库完成了折线图表的绘制,通过向MySQL数据库中引入老师提供的sql文件来获取了全国的疫情信息,然后再通过访问echart官网学习了它的基本结构以及各项结构的功能,并运行了官网的实例来更清楚的了解echarts。首先依然是在后台先连接数据库,然后写bean,不同的是需要写两个bean,一个是存放数据库中的对象,另一个则是存...

Python多线程----线程池以及线程实现异步任务

Python多线程----线程池 需求:假设我们现在有一个多线程项目,每有一个用户连接进来,我们的服务器就会创建一个线程。而我们的服务器最多能够承载100个线程,再多就会崩溃。为了防止恶意用户伪装真实用户构建大量的访问来让我们的服务器崩溃,现在需要对线程数量进行限制,一共只有100个线程,并且当一个用户访问结束以后线程会自动归还,等待下一个用户访问。如果1...