爆零!

Doors_Cross @ 2024-02-16 09:13:46

#include<iostream>
typedef long long L;
int a[100005],b[100005],c[100005];
using namespace std;
L w(L a,L b,L c)
{
    if((a<=0 || b<=0 || c<=0) || ((a<=0 || b<=0 || c<=0) && (a<b && b<c)))
    {
        return 1;
    }
    else if(a>20 || b>20 || c>20)
    {
        return w(20,20,20);
    }
    else if(a<b && b<c)
    {
        return w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    }
    else
    {
        return w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    }
}
int main()
{
    int i=0,l=-1;
    while(true)
    {
        cin>>a[i]>>b[i]>>c[i];
        if(a[i]==-1 && b[i]==-1 && c[i]==-1)
        {
            break;
        }
        i++;
    }
    for(int j=0;j<i;j++)
    {
        cout<<"w("<<a[j]<<", "<<b[j]<<", "<<c[j]<<") = "<<w(a[j],b[j],c[j])<<endl;
    }
}

by _Haoomff_ @ 2024-02-16 09:33:02

@Doors_Cross 这题要用记忆化，不然TLE。a，b，c要开long long，自己去看数据规模与约定

by liqiu_ @ 2024-02-16 09:33:40

输入的数也开 long long，可以试试。TLE 是因为你没有用记忆化搜索。

by Doors_Cross @ 2024-02-16 10:45:35

@Haoomff

#include<iostream>
typedef long long L;
L a[100005],b[100005],c[100005];
int N[25][25][25];
using namespace std;
L w(L a,L b,L c)
{
    if((a<=0 || b<=0 || c<=0) || ((a<=0 || b<=0 || c<=0) && (a>20 || b>20 || c>20)))
    {
        if(N[a][b][c]!=0)
        {
            return N[a][b][c];
        }
        else
        {
            N[a][b][c]=1;
            return N[a][b][c];
        }

    }
    else if(a>20 || b>20 || c>20)
    {
        if(N[a][b][c]==0)
        {
            N[a][b][c]=w(20,20,20);
            return N[a][b][c];
        }
        else return N[a][b][c];

    }
    else if(a<b && b<c)
    {
        if(N[a][b][c]==0)
        {
            N[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
            return N[a][b][c];
        }
        else return N[a][b][c];
    }
    else
    {
        if(N[a][b][c]==0)
        {
            N[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
            return N[a][b][c];
        }
        else return N[a][b][c];
    }
}
int main()
{
    int i=0,l=-1,s=1,x;
    while(true)
    {
        cin>>a[i]>>b[i]>>c[i];
        if(a[i]==-1 && b[i]==-1 && c[i]==-1)
        {
            break;
        }
        i++;
    }
    for(int j=0; j<i; j++)
    {
        if(a[j]==b[j] && b[j]==c[j])
        {
            for(int q=0; q<a[j]; q++)
            {
                s*=2;
            }
            cout<<"w("<<a[j]<<", "<<b[j]<<", "<<c[j]<<") = "<<s<<endl;
            continue;
        }
        cout<<"w("<<a[j]<<", "<<b[j]<<", "<<c[j]<<") = "<<w(a[j],b[j],c[j])<<endl;
    }
}

改了一下，RE+WA了，还是爆零

by _Haoomff_ @ 2024-02-16 10:55:55

@Doors_Cross a，b，c没必要用数组，可以边输入边输出结果

by _Haoomff_ @ 2024-02-16 10:57:11

@Doors_Cross 记忆化的时候不需要每次在一个条件内都判断一次N[a][b][c]是否有值，只需要在最前面判断一下即可