大佬们我超时了

P1255 数楼梯

mcmahaoran @ 2024-01-24 19:30:21

#include<bits/stdc++.h>
using namespace std;
char a1[10001], b1[10001];
int a[10001],b[10001],c[10001];
int l1(int n)
{
    if(n==1)
    {
        return 1;
    }
    if(n==2)
    {
        return 2;
    }
    else 
    {
        return l1(n-1)+l1(n-2);
    }
}
int main()
{
    int n;
    cin>>n;
    cout<<l1(n);
    return 0;
}

by AC_love @ 2024-01-24 19:32:17

你这玩意每递归一层都翻一倍,复杂度 O(2^n),你不 T 谁 T

加个记忆化吧


by xiaoshumiao @ 2024-01-24 19:32:47

@mcmahaoran

  1. 直接递归会超时,要用记忆化。

  2. 要用高精度。


by AC_love @ 2024-01-24 19:33:43

而且显然这玩意会爆 __int128,应该写个高精


|