2298. 俄罗斯“套猫”的无限套娃计划
1000ms
256MB
简单
递归算法
题目描述
在喵星人的世界里，最近流行起了一种叫“套猫”的合影游戏。有一只体重为 $n$ 公斤的特大号胖橘猫想要参与合影，它需要按照以下规则在自己的**左边**排出一队较轻的猫咪：
1. **体重要求**：紧挨着胖橘左边的猫咪，其体重必须是正整数，且**不能超过胖橘体重的一半**。
2. **无限套娃**：新加入的猫咪可以在它的左边继续套更小的猫，规则同样是“左边猫的体重不能超过右边猫的一半”。
3. **游戏结束**：这个递推过程会一直持续下去，直到最左边的猫咪太轻，无法再在其左边塞入任何正整数体重的猫咪为止。
4. **不作处理**：胖橘自己孤零零地站着（即左边没有其他猫咪）也算作一种合影方式。
现在，给定胖橘的体重 $n$，请你写个程序帮胖橘算一算，它一共有多少种不同的“套猫”合影方案？
输入格式
一行，包含一个正整数 $n$ ($1 \lt n \le 100$)，代表胖橘的初始体重。
输出格式
一行，输出一个整数，表示不同的“套猫”合影方案总数。
样例 1
输入 (Input)
6
输出 (Output)
6
- 数据范围：$1 \lt n \le 100$。
- **样例说明**：
当胖橘体重为 6 时，共有 6 种不同的排队合影方案（数字代表各猫的体重，从左往右排列）：
1. `6` (胖橘自己，不作处理)
2. `1 6` (左边加 1 公斤的猫)
3. `2 6` (左边加 2 公斤的猫)
4. `1 2 6` (在 2 6 左边继续套 1 公斤的猫，因为 $1 \le 2/2$)
5. `3 6` (左边加 3 公斤的猫)
6. `1 3 6` (在 3 6 左边继续套 1 公斤的猫，因为 $1 \le 3/2$)
- **算法提示**：
设 $f(i)$ 表示以体重为 $i$ 的猫咪作为最右侧边界时能生成的合法队列数。因为在它左边可以放任意一只体重在 $[1, \lfloor i/2 floor]$ 范围内的猫咪 $j$，所以有状态转移方程：
$$f(i) = 1 + \sum_{j=1}^{\lfloor i/2 floor} f(j)$$
其中 $\lfloor x floor$ 表示向下取整，初始状态 $f(1) = 1$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功