全部MLE，关于记忆化的一些提问

Rainsleep @ 2022-06-23 21:59:33

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll x,y,z;

ll memory[30][30][30];

ll res;

ll f(ll x,ll y,ll z)
{
    if(memory[x][y][z])
        return memory[x][y][z];
    else
    {
        if(x<=0 or y<=0 or z<=0)
            return memory[x][y][z]=1;
        else if(x>20 or y>20 or z>20)
                return memory[20][20][20]=memory[x][y][z]=f(x,y,z);
        else if(x<y and y<z)
            return memory[x][y][z]=f(x,y,z-1)+f(x,y-1,z-1)+f(x,y-1,z);
        else
            return memory[x][y][z]=f(x-1,y,z)+f(x-1,y-1,z)+f(x-1,y,z-1)-f(x-1,y-1,z-1);
    }
}

signed main()
{

    while(~scanf("%lld %lld %lld",&x,&y,&z) and (x!=-1 and y!=-1 and z!=-1))
    {
        memset(memory,0,sizeof memory);

        printf("w(%lld, %lld, %lld) = ",x,y,z);

        if(x>20)
            x=21;
        if(y>20)
            y=21;
        if(z>20)
            z=21;

        res=f(x,y,z);

        printf("%lld",res);

        puts("");

    }

    return 0;
}

by Rainsleep @ 2022-06-23 22:01:03

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll x,y,z;

ll memory[30][30][30];

ll res;

ll f(ll x,ll y,ll z)
{
    if(memory[x][y][z])
        return memory[x][y][z];
    else
    {
        if(x<=0 or y<=0 or z<=0)
            return memory[x][y][z]=1;
        else if(x>20 or y>20 or z>20)
            if(memory[20][20][20])
                return memory[20][20][20];
            else
                return memory[20][20][20]=memory[x][y][z]=f(x,y,z);
        else if(x<y and y<z)
            return memory[x][y][z]=f(x,y,z-1)+f(x,y-1,z-1)+f(x,y-1,z);
        else
            return memory[x][y][z]=f(x-1,y,z)+f(x-1,y-1,z)+f(x-1,y,z-1)-f(x-1,y-1,z-1);
    }
}

signed main()
{

    while(~scanf("%lld %lld %lld",&x,&y,&z) and (x!=-1 and y!=-1 and z!=-1))
    {
        memset(memory,0,sizeof memory);

        printf("w(%lld, %lld, %lld) = ",x,y,z);

        if(x>20)
            x=21;
        if(y>20)
            y=21;
        if(z>20)
            z=21;

        res=f(x,y,z);

        printf("%lld",res);

        puts("");

    }

    return 0;
}

改了一个细节，不过无伤MLE大雅

by Technablode @ 2022-06-23 22:01:24

前面有小于0和大于20的不要加记忆化，会爆掉

by StarLbright40 @ 2022-06-23 22:25:03

为什么要 memset 呢 虽然这或许无关紧要

by Rainsleep @ 2022-06-23 22:36:26

@Technablode 我没看懂，您能解释一下什么意思吗

by Technablode @ 2022-06-24 08:41:27

@Rainsheeep 万一有一个-114514，-114514，-114514的数据，你引用当前位置的内存就爆掉了

by qkqwork @ 2022-10-11 13:16:49

return memory[20][20][20]=memory[x][y][z]=f(x,y,z);

这里memory[x][y][z]会爆