相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4621
神犇题解：http://m.blog.csdn.net/article/details?id=52107091
解题报告
想了两个小时，确定是 $ O({n^2})$ 的DP，但就是推不出来式子 QwQ
观察最终的序列可以发现其有一下性质
- 数的相对位置与原本的位置相同
- 一种数字一定是连续的一段
更近一步，不难发现：满足上述条件的式子一定可以通过合法的操作构造出来
于是我们就可以DP了：$ f(i,j)$ 表示用了i个位置，进行了j次操作的方案数
对于原序列上的每一个数，枚举所有合法的存在区间 $ (l,r)$ 并进行转移$ f(r,j) + = f(l – 1,j – 1)$
于是就可以 $ O(n^3)$ DP辣！