WA求助！！！

zmhjason @ 2024-01-25 14:57:38

#include <bits/stdc++.h>
using namespace std;
int dp[100002];
int fib(long long x){
    if(dp[x]==0){
        if(x==1||x==2)dp[x]=x;
        else dp[x]=fib(x-1)+fib(x-2);
    }
    return dp[x];
}
int main()
{
    long long a;
    cin>>a;
    cout<<fib(a);
    return 0;
}

by timmyliao @ 2024-01-25 15:10:04

题目分析 一道简单的 递推题 一次可以走一级或两级阶梯，（突然想起《少年班》这部电影里那个人拿着个乌龟壳就算出来了…）首先我们来推一下递推式：

0级阶梯： 零种

一、1级阶梯： 1 共一种

二、2级阶梯： 1 1 2 共两种

三、3级阶梯： 1 1 1 1 2 2 1 共三种

四、4级阶梯 1 1 1 1 1 1 2 1 2 1 2 1 1 2 2 共五种

继续： 然后大家再往下推，就可以发现这是斐波那契数列（fib），非常友好： f[i] = f[i - 1] + f[i - 2]

定睛一看数据范围，N <= 5000??（要命） fib数列加到后面肯定溢出（long long类型加也只能50分），那肯定得用高精度加高精度运算了（不会超时，相信CPU，我最慢的也只有12ms）。另外为了递推方便f[0]设为1，遇到N=0就特判好了。 高精度加单精度运算不会戳这：https://blog.csdn.net/lightningcs/article/details/119542002 AC

#include<cstdlib>
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 5005;
int n;
string f[MAXN]; //开string类型存储
int a1[MAXN], a2[MAXN]; //高精运算用

string jiafa(string s1, string s2) {
    string ans;
    int len1 = s1.size();
    int len2 = s2.size();
    for (int i = 0; i < len1; i++) {
        a1[i] = s1[len1 - 1- i] - '0';
    }
    for (int i = 0; i < len2; i++) {
        a2[i] = s2[len2 - 1 - i] - '0';
    }

    len1 = max(len1, len2);
    for (int i = 0; i < len1; i++) {
        a1[i] += a2[i]; //加法
    }
    for (int i = 0; i < len1; i++) {
        a1[i + 1] += a1[i] / 10;
        a1[i] %= 10; //处理一下进位
    }
    while (a1[len1]) {
        a1[len1 + 1] += a1[len1] / 10;
        a1[len1] %= 10; //处理一下进位导致的长度增加
        len1++; 
    }
    for (int i = len1 - 1; i >= 0; i--) {
        ans += a1[i] + '0'; //累加到字符串上
    }
    return ans;
}

int main()
{
    cin >> n;
    f[0] = "1", f[1] = "1";
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 2; i <= n; i++) {
        f[i] = jiafa(f[i - 1], f[i - 2]); //高精度递推NB~！
    }

    cout << f[n] << endl;
    return 0;
}

希望能回关

by chen_kun @ 2024-01-25 15:10:59

@zmhjason 要用高精度不然会爆

by __xxy_free_ioi__ @ 2024-01-25 15:33:08

@zmhjason 这道题是必须要用高精度的

by __xxy_free_ioi__ @ 2024-01-25 15:36:35

@zmhjason 算法标签也说了要用高精度。。。

by zmhjason @ 2024-03-16 16:14:30

@timmyliao 嗯栓~