本芷若第一次做普及题，全TLE，请指正。QAQ

makeway @ 2024-12-07 17:39:19

#include<bits/stdc++.h>
using namespace std;
long long int e,f,g;
long long int w(long long int a,long long int b,long long int 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(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()
{
    while(1)
    {
    cin>>e>>f>>g;
    if(e!=-1&&f!=-1&&g!=-1)
    cout<<"w("<<e<<","<<f<<","<<g<<")="
    <<w(e,f,g)<<"\n";
    else break;
    }
    return 0;
}

by niuniudundun @ 2024-12-07 17:40:39

@makeway用记忆化搜索。

by makeway @ 2024-12-07 17:41:54

@niuniudundun 没学................

by sdjjdjdjdjd @ 2024-12-07 17:43:56

@makeway把已知答案放到数组里，如下

typedef long long ll;
int ans[21][21][21];
int m(ll a,ll b,ll c)
{
    if(a<=0||b<=0||c<=0) return 1;
    else if(a>20||b>20||c>20) return m(20,20,20);
    if(ans[a][b][c]!=-1) return ans[a][b][c];
    if(a<b&&b<c) return ans[a][b][c]=m(a,b,c-1)+m(a,b-1,c-1)-m(a,b-1,c);
    else return ans[a][b][c]=m(a-1,b,c)+m(a-1,b-1,c)+m(a-1,b,c-1)-m(a-1,b-1,c-1);
}

by niuniudundun @ 2024-12-07 17:44:24

@makeway就是开个数组记录结果，记录过得，直接用，没记录的，记录后再用。

by yuyongling @ 2024-12-07 17:44:42

[吃瓜]

by makeway @ 2024-12-07 17:52:22

@sdjjdjdjdjd 听取WA声一片（0分）

#include<bits/stdc++.h>
using namespace std;
long long int e,f,g;
int ans[21][21][21];
long long int w(long long int a,long long int b,long long int c)
{
    if(a<=0||b<=0||c<=0) return 1;
    else if(a>20||b>20||c>20) return w(20,20,20);
    if(ans[a][b][c]!=-1) return ans[a][b][c];
    if(a<b&&b<c) return ans[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    else return ans[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);
}
int main()
{
    while(1)
    {
    cin>>e>>f>>g;
    if(e!=-1&&f!=-1&&g!=-1)
    cout<<"w("<<e<<","<<f<<","<<g<<")="
    <<w(e,f,g)<<"\n";
    else break;
    }
    return 0;
}

by makeway @ 2024-12-07 17:55:28

@sdjjdjdjdjd样例都过了！！！！？？？？

by sdjjdjdjdjd @ 2024-12-07 18:01:13

给你看看我的ac代码

#include<stdio.h>
#include<string.h>
typedef long long ll;
int ans[21][21][21];
int m(ll a,ll b,ll c)
{
    if(a<=0||b<=0||c<=0) return 1;
    else if(a>20||b>20||c>20) return m(20,20,20);
    if(ans[a][b][c]!=-1) return ans[a][b][c];
    if(a<b&&b<c) return ans[a][b][c]=m(a,b,c-1)+m(a,b-1,c-1)-m(a,b-1,c);
    else return ans[a][b][c]=m(a-1,b,c)+m(a-1,b-1,c)+m(a-1,b,c-1)-m(a-1,b-1,c-1);
}
int main()
{
    memset(ans,-1,sizeof(ans));
    //for(int i=0;i<=20;i++) for(int j=0;j<=20;j++) ans[0][i][j]=ans[i][0][j]=ans[i][j][0]=1;
    ll a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    while(a!=-1||b!=-1||c!=-1){
        printf("w(%lld, %lld, %lld) = %d\n",a,b,c,m(a,b,c));
        scanf("%lld%lld%lld",&a,&b,&c);
    }
}

by xiezt123456 @ 2024-12-07 18:04:32

@makeway

#include <iostream>
#include <unordered_map>
using namespace std;

// 定义一个哈希表用于记忆化
unordered_map<string, long long> memo;

long long w(long long a, long long b, long long c) {
    // 将参数转换为字符串作为键值
    string key = to_string(a) + "," + to_string(b) + "," + to_string(c);

    // 如果结果已经在记忆化表中，直接返回
    if (memo.find(key) != memo.end()) {
        return memo[key];
    }

    // 基本情况处理
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);

    long long result;
    if (a < b && b < c) {
        result = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    } else {
        result = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    }

    // 将结果存入记忆化表
    memo[key] = result;
    return result;
}

int main() {
    long long a, b, c;
    while (true) {
        cin >> a >> b >> c;
        if (a == -1 && b == -1 && c == -1) break;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
    }
    return 0;
}

by makeway @ 2024-12-07 21:33:28

@sdjjdjdjdjd https://www.luogu.com.cn/team/87533求大佬加团