按题目分支写递归函数，并用 lru_cache 记忆化 1 到 20 范围内的重复状态。
OJ: luogu
题目 ID: P1464
难度:普及/提高-
标签:记忆化搜索递归动态规划python
日期: 2026-06-21 13:06
题意
按题目给出的分支规则定义函数 w(a,b,c)。输入多组 a,b,c，输出对应函数值，直到 -1 -1 -1 结束。
思路
直接递归会重复计算大量状态。注意题目给出两个边界：
- 只要有一个参数
<= 0，答案就是1； - 只要有一个参数
> 20，答案等于w(20,20,20)。
因此真正需要缓存的状态只在 1..20 的立方体内，最多 8000 个。
按题目顺序写递归分支，再加记忆化即可。
状态示例
| 输入 | 使用规则 | 结果 |
|---|---|---|
w(1,1,1) |
普通分支 | 2 |
w(2,2,2) |
普通分支，会复用小状态 | 4 |
w(30,-1,0) |
先命中 <=0 |
1 |
w(30,30,30) |
压到 w(20,20,20) |
固定缓存值 |
Python 知识
@lru_cache(None)是记忆化搜索的标准工具。- 多组输出先放进
answers，最后"\n".join(answers)一次输出。 - 边界判断顺序必须严格照题目来写。
参考笔记：
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
代码
python
import sys
from functools import lru_cache
@lru_cache(None)
def w(a, b, c):
if a <= 0 or b <= 0 or c <= 0:
return 1
if a > 20 or b > 20 or c > 20:
return w(20, 20, 20)
if a < b < c:
return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
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)
)
answers = []
for line in sys.stdin:
a, b, c = map(int, line.split())
if a == -1 and b == -1 and c == -1:
break
answers.append(f"w({a}, {b}, {c}) = {w(a, b, c)}")
print("\n".join(answers))复杂度
有效状态最多
总结
这题的难点不是递归式，而是避免重复计算，并且严格处理 <=0 与 >20 的边界顺序。