题目描述
如果一个排列每个位置上的逆序对个数都 \(\leq k\)，那么它是好排列。假设你有排列 \(P\)，每次可以交换两个相邻元素，用最小的步数得到好排列 \(P'\)
现给定 \(P'\) 和 \(k\)，求可能的 \(P\) 有多少个。
\(n\leq 5000\)
解法
首先考虑知道了排列 \(P\) 怎么求出排列 \(P'\)，设第 \(i\) 个位置的逆序对个数是 \(x_i\)，因为一次交换最多让逆序对减一，所以答案下界是 \(\sum_i\max(x_i-k,0)\)，构造方法是每次找到最小的位置 \(i\) 满足 \(p_{i-1}>p_i\)，并且 \(x_i>k\)，把这两个位置交换一下，可以证明如果排列不合法一定能找到这样的位置。
那么考虑用排列 \(P'\) 还原出可能的 \(P\)，首先我声明：如果我们知道了每个位置上的逆序对个数，那么对应的排列是唯一的。所以我们考察调整后的逆序对个数是否合法即可。
对于 \(x_i<k\) 的位置是不能主动换的，因为交换让逆序对增加或减小都是不合法的，让他们的逆序对固定即可。对于 \(x_i=k\) 的位置逆序对是可以任意增加的，但就是不能减小，所以如果我们按照 \(i=n...1\) 的顺序考虑，我们可以把它右移任意步数，那么乘上 \((n-i+1)\) 即可。
总结
最优策略问题也可以思考构造答案下界，但是首先一定要想清楚答案下界是什么。
计数题中的转化要建立起对应关系，比如这题我们建立了逆序对和排列的对应关系，就把问题转化到逆序对上了。