1

之前的一些废话：《摔跤吧爸爸》这部电影真是太感动了

题解：还是觉得这种题挺难的，考试时候想不到正解的话花几分钟把30分拿了其实也挺爽的。

控制交换次数为n-1，所以我们可以这么考虑：考虑倒着处理，比如交换 (i, i + 1)，那么前面的所有数不管怎么交换都无法到后面去(下标恒小于等于 i)，后面的数也是一样到不了前面。说明这最后一次交换前，就要求对于所有的 x <= i, y > i，px<py。所以交换前左边的数是连续的，右边也是连续的。由于交换前，前面和后面的数是互相不干涉的，所以就归结成了两个子问题。（这段话是搬运题解而来的）

想到这里，就不太难了，很明显的区间DP：dp[i][j]表示将当前序列的第i个数到第j个数换成最终序列的方案数，只要区间长度确定了，那么交换次数也确定了，所以没有必要再单开一个状态来存交换次数。根据区间DP的套路，转移肯定是枚举中间点，但是还有一个限制：假如要在[L,R]中选取第k和第k+1个数进行交换，那么交换之后[L,K]中的数是再也不可能换到K以后了的，[K+1,R]中的数也不可能换到K+1以前了，所以需要保证交换第k和第k+1个数后，新序列中[L,K]的数都小于等于K，而[K+1,R]的数都大于K。只有满足以上限制的才能进行转移。转移方程是：dp[L,R]+=dp[L,K]*dp[K+1,R]*C(R-L,K-L-1),至于为什么要乘上一个组合数...自己想一想吧。

然后需要一个组合数预处理。

代码：目前暂时无法得到。。

总结：突破口在于控制交换次数，算是一种经验吧。

某次模拟赛 交换