P1464 Function

题目链接：

本题为一道极其经典的记忆化搜索模板题，务必搞懂并掌握记忆化搜索的常见书写格式。

主要思想就是用一个 \(dp\) 数组将每一个 \(w\) 函数的值存储起来，下一次检查 \(dp[a][b][c]\) 的值，如果已经算过就直接调用，可节省大量时间。

#include <cstdio>

using LL = long long;

LL dp[25][25][25];

LL w(LL a, LL b, LL c) {
	if (a <= 0 || b <= 0 || c <= 0) return 1;
	if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
	if (dp[a][b][c]) return dp[a][b][c];
	if (a < b && b < c) {
		return dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
	}
	return 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);
}

int main()
{
	LL a, b, c;
	while (scanf("%lld%lld%lld", &a, &b, &c) != EOF) {
		if (a == -1 && b == -1 && c == -1) return 0;
		printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a, b, c));
	}
}

值得注意的一点是，若把判断语句写在函数一开始，还需先判断一下 \(a,b,c\) 是否合法。

LL w(LL a, LL b, LL c) {
    if (a >= 0 && a <= 25 && b >= 0 && b <= 25 && c >= 0 && c <= 25 && dp[a][b][c] != 0) return dp[a][b][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) {
		return dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
	}
	return 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);
}