[CEOI2016]kangaroo其实就是给你一个\(p_1,p_n\)确定，其余未知的排列，求有多少个合法的排列，满足一个数要么比他相邻的两边都大，要么比他相邻的两边都小。我们若是依次考虑每\(p_{1,2,\cdots,n}\)，由于他的取值还和后面有关，我们不好考虑，考虑依次将\(i=1,2,\cdots,n\)填入当前的序列

题目大意求出有多少种排列\(p\)满足对于任意\(i\in(1,n)\)有\(p_i\)两侧的值同时大于或小于\(p_i\)。规定\(p_1=s,p_n=t\)。\(2\leqn\leq2\times10^3，1\leqs,t\leqn\)思路首先能看出是动态规划。但是如果纯区间动规的话不太好转移，因为无法使得两个区间拼接的部分

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

分析一个妙妙的trick。首先原题可以转化成求有多少\(1\simn\)的排列\(p\)满足\(\foralli\in(1,n)\)，\(p_i\)两边的数同时小于或大于\(p_i\)，且\(p_1=s,p_n=t\)

前言有些题目照常DP不是很好做，感觉像是区间DP，但是怎么设状态都不好转移，那么可以考虑一种维护块儿的DP，就是这道题要用到的知识点。背景分析如果每次跳跃的点的编号形

感觉这样的\(\text{dp}\)题还比较多，思路都比较的神奇。个人感觉比较像区间\(\text{dp}\)的一类变种。但又和区间\(\text{dp}\)的维护方式极不一样。对于此类\(\t