題目描述
如果一個排列每個位置上的逆序對個數都 \(\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)\) 即可。
總結
最優政策問題也可以思考構造答案下界，但是首先一定要想清楚答案下界是什麼。
計數題中的轉化要建立起對應關系，比如這題我們建立了逆序對和排列的對應關系，就把問題轉化到逆序對上了。