为什么用了高精还是50分啊

natie @ 2024-07-18 10:44:11

#include<bits/stdc++.h>
using namespace std;
int a[5010],b[5010],c[5010];
int main()
{
    int n,f=0,f1=1;
    string x="0",y;
    cin>>n;
    int lx=1,ly,ansl;
    for(int i=1;i<=n;i++)
    {
        if(i%2)
        {
            f=f+f1;
            y=to_string(f);
        }
        else
        {
            f1=f+f1;
            y=to_string(f1);
        }
        int lx=x.size();
        int ly=y.size();
        for(int i=lx-1,j=1;i>=0;i--,j++)
        {
            a[j]=x[i]-'0';
        }
        for(int i=ly-1,j=1;i>=0;i--,j++)
        {
            b[j]=y[i]-'0';
        }
        ansl=max(lx,ly);
        for(int i=0;i<=ansl;i++)
        {
            c[i]+=a[i]+b[i];
            c[i+1]=c[i]/10;
            c[i]%=10;
        }
    }
    for(int i=ansl+1;i>0;i--)
    {
        if(i==ansl+1&&c[i]==0)
        {
            i--;
        }
        cout<<c[i];
    }
    return 0;
 }

by Lijunzhuo @ 2024-07-18 10:46:32

重构吧

by sdwhl @ 2024-07-18 10:46:54

递推式是啥，写对了吗

by natie @ 2024-07-18 10:51:17

@Lijunzhuo @sdwhl

好吧

by King_and_Grey @ 2024-07-18 10:54:13

@natie 注意部分：

dp[1] = Bigint(1);
dp[2] = Bigint(2);
for(int i = 3; i <= n ;i++){
    dp[i] = dp[i - 1] + dp[i - 2]; 
}

高精度结构体：

const int maxn = 5010;
struct Bigint {
    int len, a[maxn];
    Bigint(int x = 0) {
        memset(a, 0, sizeof(a));
        for (len = 1; x; len++)
            a[len] = x % 10, x /= 10;
        len--;
    }
    int &operator[](int i) {
        return a[i];
    }
    void flatten(int L) {
        len = L;
        for (int i = 1; i <= len; i++)
            a[i + 1] += a[i] / 10, a[i] %= 10;
        for (; !a[len]; )
            len--;
    }
    void print() {
        for (int i = max(len, 1); i >= 1; i--)
            printf("%d", a[i]);
    }
};
Bigint operator+(Bigint a, Bigint b) {
    Bigint c;
    int len = max(a.len, b.len);
    for (int i = 1; i <= len; i++)
        c[i] += a[i] + b[i];
    c.flatten(len + 1);
    return c;
}

by King_and_Grey @ 2024-07-18 10:55:24

@natie 写错了，是主要部分……

递推式：dp[i] = dp[i - 1] + dp[1 - 2]

by natie @ 2024-07-18 11:02:45

@greyandking

非常感谢

by King_and_Grey @ 2024-07-18 11:04:23

@natie 没关系