请问为啥会超时呀

P1464 Function

adksla @ 2023-12-20 09:10:24

#include<iostream>
using namespace std;

int jiyi[30][30][30] = {0};
int w(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 w(20,20,20);
    else if(jiyi[a][b][c]==0){
        if(a<b&&b<c) jiyi[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
        else jiyi[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 jiyi[a][b][c];
    }

}

int main(){
    long long a,b,c;
    while(1){
        cin >> a >> b >> c;
        if(a==-1&&b==-1&&c==-1){
            break;
        }
        int ans = w(a,b,c);
        printf("w(%d,%d,%d) = %d",a,b,c,ans);
    }

}

by xiaoshumiao @ 2023-12-20 10:12:49

@adksla 当 jiyi_{a,b,c}\ne 0 时 w 函数没返回值。


by hxd2011 @ 2023-12-30 10:40:45

可以试一下记忆化递归呀


|