wangruize88 @ 2024-05-12 11:19:06

#include <iostream>
#include <stdio.h>
using namespace std ;
long long 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 ( 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 () {
    long long a , b , c ;
    while ( cin >> a >> b >> c ) {
        if ( a == -1 && b == -1 && c == -1 ) break ;
        printf ( "w(%lld, %lld, %lld) = %lld" , a , b , c , w(a,b,c) ) ;
    }
    return 0 ;
}

by _C_ccx_N_ @ 2024-05-12 11:24:01

递归不超时就怪了

by zhouzihang1 @ 2024-05-12 11:27:52

@wangruize88 记忆化搜索

by markkkk @ 2024-05-12 12:43:38

时间复杂度太高了

by Vincent615 @ 2024-05-12 12:49:55

记忆化：

禁止抄袭，仅供借鉴

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll arr[100][100][100];
bool vis[100][100][100];
ll func(ll a,ll b,ll c){
    if(a<=0 or b<=0 or c<=0)
        return 1;
    if(a>20 or b>20 or c>20)
        return func(20,20,20);
    if(vis[a][b][c]) 
        return arr[a][b][c];
    if(a<b and b<c)
        arr[a][b][c]=func(a,b,c-1)+func(a,b-1,c-1)-func(a,b-1,c);
    else
        arr[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);
    vis[a][b][c]=true;
    return arr[a][b][c];
}
int main(){
    ll a,b,c;
    while(true){
        cin>>a>>b>>c;
        if(a==-1&&b==-1&&c==-1)
            break;
        printf("w(%ld, %ld, %ld) = %ld\n",a,b,c,func(a,b,c));
    }
    return 0;
}