洛谷P1464 题解

传送门（不谢）

第一种思路：模拟

题目让我们做什么我们就做什么，然后嘛……很轻松就可以得到代码：

#include<iostream>
#include<cstdio>
#define ll long long
#define f(i,a,b) for(int i = a ; i <= b ;i ++ )
using namespace std;
ll a,b,c ;
ll w(int a,int b,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( scanf("%lld%lld%lld",&a,&b,&c) == 3 )
    {
        if( a == -1 && b == -1 && c == -1 ) break ;
        cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<w(a,b,c)<<endl;
    }
    return 0 ;
}

但是呢，当我们输入15 15 15时……呵呵……呵……超时了

所以呢，我们要进行优化。

我们发现：有些组合被我们计算了多次，所以……我们考虑记忆化

就多一个变量和一点代码嘛……

以下是AC代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll dp[25][25][25];
ll a,b,c;
ll w(ll a,ll b,ll c)
{
    if(a<=0||b<=0||c<=0) return 1;
    else if(dp[a][b][c]!=0) return dp[a][b][c];
    else if(a>20||b>20||c>20) dp[a][b][c]=w(20,20,20);
    else if(a<b&&b<c) dp[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    else dp[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 dp[a][b][c];
}
int main()
{
    while(scanf("%lld%lld%lld",&a,&b,&c)==3)
    {
        if( a==-1 && b==-1 && c==-1 ) break;
        printf("w(%lld, %lld, %lld) = ",a,b,c);
        if(a>20) a=21;
        if(b>20) b=21;
        if(c>20) c=21;
        printf("%lld\n",w(a,b,c));
    }
    return 0;
}

洛谷P1464 题解

原文：https://www.cnblogs.com/Lwen1243/p/12276143.html