TLE求看

IaLWH @ 2024-08-07 15:58:31

#include<cstdio>
#define int long long

int w(int a,int b,int c){
    if(a<=0||b<=0||c<=0)
        return 1;
    if(a>20||b>20||c>20)
        return w(20,20,20);
    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);
}
signed main(){
    int i,a=0,b=0,c=0;
    scanf("%d%d%d",&a,&b,&c);
    for(i=0;a!=-1||b!=-1||c!=-1;i++){
        printf("w(%d, %d, %d) = %d\n",a,b,c,w(a,b,c));
        scanf("%d%d%d",&a,&b,&c);
    }
    return 0;
}

by zhuyucheng6046 @ 2024-08-07 16:01:55

@IaLWH 你这个要用记忆化，单纯去递归会超时。我给你写一下代码

by IaLWH @ 2024-08-07 16:03:48

@zhuyucheng6046 我只是想知道为什么样例都会超时

by Gcc_Gdb_7_8_1 @ 2024-08-07 16:06:39

你用 scanf 输入 long long 不应该用 %lld 吗?

by Gcc_Gdb_7_8_1 @ 2024-08-07 16:07:55

改完后就 AC 样例了

by xujiacheng0312 @ 2024-08-07 16:08:21

@IaLWH 单纯递归会有许多重复计算，才会TLE;
用记忆化呢减少计算量

by Gcc_Gdb_7_8_1 @ 2024-08-07 16:11:39

要不要 AC Code?

by Gcc_Gdb_7_8_1 @ 2024-08-07 16:12:57

@IaLWH ?

by GrainRain25 @ 2024-08-07 16:15:57

#include<cstdio>
#define int long long
int f[25][25][25];

int w(int a,int b,int c){
    if(a<=0||b<=0||c<=0)
        return 1;
    if(a>20||b>20||c>20)
        return (f[20][20][20]?f[20][20][20]:f[20][20][20]=w(20,20,20));
    if(!f[a-1][b][c]) f[a-1][b][c]=w(a-1,b,c);
    if(!f[a-1][b-1][c]) f[a-1][b-1][c]=w(a-1,b-1,c);
    if(!f[a-1][b][c-1]) f[a-1][b][c-1]=w(a-1,b,c-1);
    if(!f[a-1][b-1][c-1]) f[a-1][b-1][c-1]=w(a-1,b-1,c-1);
    return f[a-1][b][c]+f[a-1][b-1][c]+f[a-1][b][c-1]-f[a-1][b-1][c-1];
}
signed main(){
    int i,a=0,b=0,c=0;
    f[0][0][0]=1;
    scanf("%lld%lld%lld",&a,&b,&c);
    for(i=0;a!=-1||b!=-1||c!=-1;i++){
        printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
        scanf("%lld%lld%lld",&a,&b,&c);
    }
    return 0;
}

没开记忆化肯定炸

输入也有问题，是%lld而不是%d

by Gcc_Gdb_7_8_1 @ 2024-08-07 16:16:53

@GrainRain25 对

by zhuyucheng6046 @ 2024-08-07 16:18:22

#include<bits/stdc++.h>
using namespace std;
long long f[25][25][25];
long long p(long long a,long long b,long long c)
{
    if(a<=0||b<=0||c<=0) return 1;
    else if(a>20||b>20||c>20) return p(20,20,20);
    else if(f[a][b][c]!=0) return f[a][b][c];
    else if(a<b&&b<c) f[a][b][c]=p(a,b,c-1)+p(a,b-1,c-1)-p(a,b-1,c);
    else f[a][b][c]=p(a-1,b,c)+p(a-1,b-1,c)+p(a-1,b,c-1)-p(a-1,b-1,c-1);
    return f[a][b][c];
}
int main()
{

    while(1)
    {long long q,w,e;
    scanf("%lld %lld %lld",&q,&w,&e);
    //cout<<q<<" "<<w<<" "<<e<<endl;
        if((q==-1)&&(w==-1)&&(e==-1))  break;
         printf("w(%lld, %lld, %lld) = %d\n", q,w,e, p(q,w,e));
    }

    return 0;
}