jzy_CSPJ_AK @ 2024-02-03 13:22:23

#include<bits/stdc++.h>

using namespace std;
long long s[25][25][25];
long long r(long long a,long long b,long long c){

    if(a<=0||b<=0||c<=0){
        return 1;
    }
    if(s[a][b][c]!=0)return s[a][b][c];
    else if(a>20||b>20||c>20)return r(20,20,20);
    else if(a<b&&b<c)return r(a,b-1,c-1)+r(a,b,c-1)-r(a,b-1,c);
    else return r(a-1,b,c)+r(a-1,b-1,c)+r(a-1,b,c-1)-r(a-1,b-1,c-1);
}
signed main(){
    long long a,b,c;
    while(true){
        cin>>a>>b>>c;
        if(a==-1&&b==-1&&c==-1)return 0;
        cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<r(a,b,c)<<endl;
    }
}

by pengbubu @ 2024-02-03 13:39:10

记忆结果

——用一个三维数组存算过的函数的结果——名[a][b][c]=xxx；（可以用return 名[a][b][c] = xxx;的方式——方便）

在函数最开始放一个串代码；

if(名[a][b][c]!=0)return 名[a][b][c];

不然运行时间会超时

by xiaoshumiao @ 2024-02-03 13:40:49

@pengbubu2026 他不是用了吗。

by xiaoshumiao @ 2024-02-03 13:42:06

改成这样：

#include<bits/stdc++.h>

using namespace std;
long long s[25][25][25];
long long r(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 r(20,20,20);
    else if(s[a][b][c]!=0)return s[a][b][c];
    else if(a<b&&b<c)return s[a][b][c]=r(a,b-1,c-1)+r(a,b,c-1)-r(a,b-1,c);
    else return s[a][b][c]=r(a-1,b,c)+r(a-1,b-1,c)+r(a-1,b,c-1)-r(a-1,b-1,c-1);
}
signed main(){
    long long a,b,c;
    while(true){
        cin>>a>>b>>c;
        if(a==-1&&b==-1&&c==-1)return 0;
        cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<r(a,b,c)<<endl;
    }
}

by pengbubu @ 2024-02-03 13:43:03

//参考代码——函数名不一样——函数部分
int easy[60][60][60] = {0};
int w(int a,int b,int c){
    if (easy[a][b][c] != 0){
        return easy[a][b][c];
    }
    //a≤0 或 b≤0 或 c≤0,则 w(a,b,c)=1 ;
    if (a <= 0 or b <= 0 or c <= 0){
        return easy[a][b][c] = 1;
    }
    //如果 a>5 或 b>5 或 c>5 ,则 w(a,b,c)=w(5,5,5) ;
    if (a>20 or b>20 or c>20){
        return easy[a][b][c] = w(20,20,20);
    }
    //如果 a<b 且 b<c ,则 w(a,b,c)=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c) ;
    if (a<b and b<c){
        return easy[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    }
        //其他情况下：w(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 easy[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);
}

by xiaoshumiao @ 2024-02-03 13:44:02

• else if(a>20||b>20||c>20)return r(20,20,20); 放在前面，否则调用 r(100,100,100) 时就会数组越界。

• 你没把 r 的值记录在 s 中，记忆化了个寂寞。

by pengbubu @ 2024-02-03 13:51:56

@xiaoshumiao 但他用了跟没用一样——只开了数组——没有记录