P1464 Function 题解

Dijkstra_zyl · 2025-09-29 21:06:36 · 题解

P1464 Function 题解

需要用到记忆化搜索

#include <bits/stdc++.h>//模拟 + 记忆化搜索 
using namespace std;
int dp[30][30][30];
long long w(long long a,long long b,long long c){
    if(a <= 0 || b <= 0 || c <= 0) return 1;
    if(a > 20 || b > 20 || c > 20) return w(20,20,20);//两个特判 
    if(a < b && b < c){//情况1  挨个录 
        if(!dp[a][b][c-1]) dp[a][b][c-1] = w(a,b,c-1);
        if(!dp[a][b-1][c-1]) dp[a][b-1][c-1] = w(a,b-1,c-1);
        if(!dp[a][b-1][c]) dp[a][b-1][c] = w(a,b-1,c);
        dp[a][b][c] = dp[a][b][c-1]+dp[a][b-1][c-1]-dp[a][b-1][c];
    }else{//情况二 挨个录 
        if(!dp[a-1][b][c]) dp[a-1][b][c] = w(a-1,b,c);
        if(!dp[a-1][b-1][c]) dp[a-1][b-1][c] = w(a-1,b-1,c);
        if(!dp[a-1][b][c-1]) dp[a-1][b][c-1] = w(a-1,b,c-1);
        if(!dp[a-1][b-1][c-1]) dp[a-1][b-1][c-1] = w(a-1,b-1,c-1);
        dp[a][b][c] = dp[a-1][b][c] + dp[a-1][b][c-1] + dp[a-1][b-1][c] - dp[a-1][b-1][c-1];
    }
    return dp[a][b][c]; 
}
int main(){
    long long a,b,c;
    while(scanf("%lld%lld%lld",&a,&b,&c)){
        if(a == -1 && b == -1 && c == -1) return 0;
        printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
    }
    return 0;
}