蓝桥杯算法训练进击的青蛙 c++

资源限制

内存限制：256.0MB C/C 时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

　　青蛙X正准备跳过一座桥，这座桥被划分为N段，记青蛙所在的起始点为0，桥的末端为N。桥上的一些点有一些石子，这些点是无法跳上去的。青蛙每次跳跃能向前跳跃 1， 2， 3段，现在请你算出跳到末端的总方法数。如果无法到达，请输出”No Way!"

输入格式

　　输入数据共N行。

　　第一行一个数字N，代表桥的长度。

　　接下来N行，表示从点1~N的道路情况，每行一个数字0或1，1表示有石子。

输出格式

　　输出一行，为一个整数，代表方法数，无法到达为“No Way!"

　　由于数据过大，我们只需要求出对 1000000007 的余数即可

输出格式

　　输出一行，为一个整数，代表方法数，无法到达为“No Way!"

　　由于数据过大，我们只需要求出对 1000000007 的余数即可

样例输入

样例输出

数据规模和约定

　　N <= 10^6

这道题一眼以为是搜索回溯，但是看了一眼数据大小就感觉会超时，提交上去运行超时，所以会有更好的算法，然后就去看了okok__TXF大佬的思路，看了他们的博客都是用的dp 递推，是斐波那契的变形。具体思路讲解看注释吧。

代码语言：javascript复制

#include<iostream>
using namespace std;
typedef long long ll;
ll dp[1000005];//dp[i]表示从第0块石头到第i块石头的方法数
ll n;
//斐波那契数列变形dp[i]=dp[i-1] dp[i-2] dp[i-3];
//此青蛙一次能跳1，2，3步，所以只要求出dp[1],dp[2],dp[3]作为初值条件，利用递归求到n即可
int main(){
    cin>>n;
    for(int i=1;i<=n;i  ){
        cin>>dp[i];
    }
    //初值条件
    dp[1]==0?dp[1]=1:dp[1]=0;
    dp[2]==0?dp[2]=dp[1] 1:dp[2]=0;
    dp[3]==0?dp[3]=dp[2] dp[1] 1:dp[3]=0;
    for(int i=4;i<=n;i  ){
        if(dp[i]==1){//如果第i点不能跳，从0点无论怎样跳都不会到达第i点
            dp[i]=0;//不能到达直接置0就可以了
        }else{
            dp[i]=(dp[i-1]00000007 dp[i-2]00000007 dp[i-3]00000007)00000007;
        }
    }
    if(dp[n]==0){//第n点根本就到达不了还有啥方法数
        cout<<"No Way!"<<endl;
    }else{//如果dp[n]不为0那就是至少有一种可以到达的方法数
        cout<<dp[n]00000007<<endl;
    }
    return 0;
}

其实刚开始我也没想到是斐波那契的变形题，只有刷题刷多了就知道了，写了斐波那契也是通过了样例

本人小白一枚，如有错误请各位大佬指出，共同进步。

数据算法 c++ dp 内存

0 人点赞

蓝桥杯 算法训练 进击的青蛙 c++

蓝桥杯算法训练进击的青蛙 c++