高精dp却 WA 0分 救。。

P1255 数楼梯

DinoCrab @ 2024-09-23 16:01:53

救命啊

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i = a;i <= b;i ++)
#define rrep(i,a,b) for(int i = a;i >= b;i --)
int read(){
    int x = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
const int mod = 1e9 + 7;
struct S{
    int v[1001];
}a[5002];
int l = -1;
void pls(int c,int x,int y){
    int l1 = 0;
    int l2 = 0;
    while(a[x].v[l1]) l1 ++;
    while(a[y].v[l2]) l2 ++;
    l = max(l1,l2);
    rep(i,0,l - 1){
        a[c].v[i] = a[x].v[i] + a[y].v[i];
        a[c].v[i + 1] = a[c].v[i] / 10;
        a[c].v[i] %= 10;
    }
    if(a[c].v[l]) l ++;
    return;
}
signed main(){
    int n = read();
    a[1].v[0] = 1;
    a[2].v[0] = 2;
    rep(i,3,n){
        pls(i,i - 1,i - 2);
    }
    l += 5;
    while(!a[n].v[l]) l --;
    rrep(i,l - 1,0) cout << a[n].v[i];
    return 0;
}

by DYF2765491381672943 @ 2024-10-09 16:07:46

高精度的话len可以定义在结构体里，避免出错还好改一点（如果只输入几个数的话其实可以不用read()的） 我自己写了个高精度，你看看吧

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int num[1050];
    int len;
}a[5050];
void add(node x,node y,int t)
{
    a[t].len=max(x.len,y.len);
    for (int i=1;i<=a[t].len;i++)
    {
        a[t].num[i]+=x.num[i]+y.num[i];
        a[t].num[i+1]+=a[t].num[i]/10;
        a[t].num[i]=a[t].num[i]%10;
    }
    if (a[t].num[a[t].len+1])a[t].len++;
    return ;
}
int main()
{
    int n;
    cin>>n;
    a[1].len=a[2].len=1;
    a[1].num[1]=1;
    a[2].num[1]=2;
    for (int i=3;i<=n;i++)
    {
        add(a[i-1],a[i-2],i);
    }
    for (int i=a[n].len;i>=1;i--)cout<<a[n].num[i];
    return 0;
 }

求个关注，谢谢

|