全TLE了!我看这题至少要有普及+/提高

caojiaming @ 2023-01-02 12:09:10

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll func(ll a,ll b,ll c)
{
    if(a<=0||b<=0||c<=0)
    {
        return 1;
    }
    else if(a>20||b>20||c>20)
    {
        return func(20,20,20);
    }
    else if(a<b&&b<c)
    {
        return func(a,b,c-1)+func(a-1,b-1,c)-func(a,b-1,c);
    }
    else
    {
        return func(a-1,b,c)+func(a-1,b-1,c)+func(a-1,b,c-1)-func(a-1,b-1,c-1);
    }
}
int main()
{
    ll a,b,c;
    while(1)
    {
        cin>>a>>b>>c;
        if(a==-1&&b==-1&&c==-1)
        {
            return 0;
        }
        cout<<"w(a, b, c) = "<<func(a, b, c)<<"\n";
    }
    return 0;
}

by liangbowen @ 2023-01-02 12:10:55

需要记忆化。您可以输入 20,20,20 应该是会TLE的。

by Alber_love_Weinstein @ 2023-01-02 12:12:08

注意看，这题考记忆化

by shoot_down @ 2023-01-02 12:12:27

@caojiaming 最多评黄吧，该题用记忆化，其实评个橙也说得过去

by caojiaming @ 2023-01-02 12:12:52

那怎么搞? @liangbowen

by Adchory @ 2023-01-02 12:14:01

@caojiaming 那个数组记录当前 dfs 状态，搜到重的直接返回就行，不过就这一个记忆化搜索是黄，/

by Adchory @ 2023-01-02 12:14:41

@Reimu_Hakurei 最后口误了，是橙

by liangbowen @ 2023-01-02 12:16:01

@caojiaming 您可以参考题解。

就是再开一个数组，记录 \operatorname{func}(a, b, c) 的值。比如说你已经查过了 (5, 6, 7)，那么下一次再调用这个函数的时候，如果你已经记录了，那么直接用数组里的值即可，就不需要再递归了。

讲得不是很清楚，但是其实是很好理解的

by Kevin_Mamba @ 2023-01-02 12:17:53

@caojiaming 你的输出也有问题吧。

by Kevin_Mamba @ 2023-01-02 12:19:53

@caojiaming

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll f[101][101][101];
ll func(ll a,ll b,ll c)
{
    if(a<=0||b<=0||c<=0)
    {
        return 1;
    }
    else if(f[a][b][c]) return f[a][b][c];
    else if(a>20||b>20||c>20)
    {
        return f[a][b][c]=func(20,20,20);
    }
    else if(a<b&&b<c)
    {
        return f[a][b][c]=func(a,b,c-1)+func(a,b-1,c-1)-func(a,b-1,c);
    }
    else
    {
        return f[a][b][c]=func(a-1,b,c)+func(a-1,b-1,c)+func(a-1,b,c-1)-func(a-1,b-1,c-1);
    }
}
int main()
{
    ll a,b,c;
    while(1)
    {
        cin>>a>>b>>c;
        if(a==-1&&b==-1&&c==-1)
        {
            return 0;
        }
        else printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,func(a,b,c));
    }
    return 0;
}

by Kevin_Mamba @ 2023-01-02 12:20:40

@2124Kobe 函数的第三种情况细节也错了，希望认真抄题干。