kangaroo

# Description 有 $n$ 个套娃，每个套娃都有外体积与内体积，内体积严格小于外体积。你可以把一个娃套到另一个内体积比它的外体积大的娃里面，并且需要套到不能再套为止。求出有多少种套娃方案。 题目链接：[JOI](https://www2.ioi-jp.org/camp/2012/2012 ......

## 前言 写这篇题解的原因是这道题提供了一种新的 dp 思路——插入 dp。 ## 题意 给定一个长为 $n$ 的数轴，一只袋鼠在上面要从 $s$ 跳到 $t$，跳跃过程中，每次跳跃方向必须与上一次相反，求方案数。 ## 分析 拿到这个题其实还是蛮蒙的，但是如果我们转化（抽象）一下题意，就会发现这 ......