Author: loop3r
Date: 20260225
tag: 递归
link: https://www.luogu.com.cn/problem/P1464

问题描述

link

分析

略

参考代码

#include<bits/stdc++.h>
using namespace std;

long long f[25][25][25];

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) {
        if (!f[a][b][c - 1]) f[a][b][c - 1] = w(a, b, c - 1);
        if (!f[a][b - 1][c]) f[a][b - 1][c] = w(a, b - 1, c - 1);
        if (!f[a][b][c - 1]) f[a][b][c - 1] = w(a, b - 1, c);
        f[a][b][c] = f[a][b][c - 1] + f[a][b - 1][c] - f[a][b][c - 1];
    } else {
        if (!f[a - 1][b][c]) f[a - 1][b][c] = w(a - 1, b, c);
        if (!f[a - 1][b - 1][c]) f[a - 1][b - 1][c] = w(a - 1, b - 1, c);
        if (!f[a - 1][b][c - 1]) f[a - 1][b][c - 1] = w(a - 1, b, c - 1);
        if (!f[a - 1][b - 1][c - 1]) f[a - 1][b - 1][c - 1] = w(a - 1, b - 1, c - 1);
        f[a][b][c] = f[a - 1][b][c] + f[a - 1][b - 1][c] + f[a - 1][b][c - 1] - f[a - 1][b - 1][c - 1];
    }
    return f[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) break;

        printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a, b, c));
    }

    return 0;
}