TLE求助！！！

xiaolanhuaaizaipei @ 2023-11-24 12:41:31

#include<bits/stdc++.h>
using namespace std;
long long a;
long long  sum;
long long f(int m,int n){
        if(m==0||n==0){
        return 1;
        }
        else
        {
        return f(m-1,n)+f(m,n-1); 
        }
}
int main() {
    cin>>a;
    int N=a;
    sum=0;
    for(int i= 0;i<=N/2;i++){
        sum= sum+f(N-2*i,i); }
    printf("%d",sum);   
}

by ltzx2022_kanxinyi_5 @ 2023-12-01 14:46:23

@xiaolanhuaaizaipei 首先这个代码格式我实在是看不下去了：

#include<bits/stdc++.h>
using namespace std;
long long n;
long long sum;
long long f(int m,int n){
    if(m==0||n==0)
        return 1;
    return f(m-1,n)+f(m,n-1);
}
int main(){
    cin>>n;
    sum=0;
    for(int i=0;i<=n/2;i++)
        sum+=f(n-2*i,i);
    printf("%d",sum);
}

微调一下，有没有感觉清爽很多。

递归做法当然是合适的，相当于你要走两遍，时间复杂度高于递推算法，这里推荐你用更快速地递推。 注：该题数据过大，需加上高精度方可AC

#include<bits/stdc++.h>
using namespace std;
int n,len=1,f[5003][5003];
void add(int k){
    for(int i=1;i<=len;i++)
        f[k][i]=f[k-1][i]+f[k-2][i];
    for(int i=1;i<=len;i++) 
        if(f[k][i]>=10){
            f[k][i+1]+=f[k][i]/10;
            f[k][i]=f[k][i]%10;
            if(f[k][len+1])
                len++;
        }
}
int main(){
    cin>>n;
    f[1][1]=1,f[2][1]=2;
    for(int i=3;i<=n;i++)
        add(i);
    for(int i=len;i>=1;i--)
        cout<<f[n][i];
    return 0;
}

AC了也别忘了给个关注呀

by xiaolanhuaaizaipei @ 2023-12-03 22:22:46

蟹蟹你