3193. 統計逆序對的數目

題目描述：

給定一個長度為n的二維數組$re$，其中$re[i]=[i{d}_i,cn{t}_i]$，求存在多少個全排列perm滿足對所有的$re[i]$都有$perm[\mathrm{0..}i{d}_i]$恰好有 $cn{t}_i$個逆序對

答案對1000000007取模

• 2 <= n <= 300
• 1 <= requirements.length <= n
• requirements[i] = [endi, cnti]
• 0 <= endi <= n - 1
• 0 <= cnti <= 400
• 輸入保證至少有一個 i 滿足 endi == n - 1 。
• 輸入保證所有的 endi 互不相同。

思路：

首先觀察題目類型是求全排列的數量，還要取模，大概率是dp

再看數據范圍 n=300,m=400，dp的狀態方程完全可以放的下二維的

所以我們考慮用$dp[i][j]$表示滿足所有$id<=i$的re下，前i個數字 逆序對數量是j 的全排列數量

求解普通逆序對時，我們可以掃一遍數組，對于每個 $ar[i]$，求出$j<i$中$ar[j]>ar[i]$的數量并求和

在本題，我們也考慮用這種方式來進行狀態的轉移

對于$i$，我們只在乎$ar[i]$在$ar[1]?ar[i]$中的大小關系，如果$ar[i]$在這$i$個數中排最大，也就是排第$i$位，則不會產生新的逆序對，即$i?i=0$，如果排最小，也就是排第1位，則會產生$i?1$個逆序對，如果排第$k$大，則會產生$i?k$個新的逆序對

所以，我們可以枚舉$ar[i]$在$ar[1]?ar[i]$排第幾來進行狀態轉移

對于狀態為$dp[i][j]$，存在兩種情況，一種是i-1層是沒有限制的，另一種是i-1層是有固定值限制的

• 如果$i?1$處沒有題目給定的逆序對數量限制，則枚舉k，從0枚舉到$min(i,j)$，$min(i,j)$是因為對于下標從0開始，到$i?1$的數組，長度為i，此時在末尾添加一個元素，逆序對一次最多只能產生$i$

  $dp[i][j]={\sum }_{k=0}^{min(i,j)}dp[i?1][j?k]$

• 如果$i?1$處存在題目給定的逆序對數量限制，那只能從那一個狀態轉移過來，假設r代表則re中對應位置的cnt， 則$dp[i][j]=dp[i?1][r]$，$r<=j<=r+i$

class Solution {const int mod = 1000000007;
public:int numberOfPermutations(int n, vector<vector<int>>& re) {vector<int>p(n, -1);for(auto x : re){p[x[0]] = x[1];}int m = p[n - 1];vector<vector<int>> dp(n, vector<int>(m + 1));dp[0][0] = 1;for(int i = 1; i < n; ++i){if(p[i - 1] == -1){//無限制for(int j = 0; j <= m; ++j){for(int k = 0; k <= min(i, j); ++k){dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;}}}else{//有限制for(int j = p[i - 1]; j <= min(m, p[i - 1] + i); ++j){dp[i][j] = dp[i - 1][p[i - 1]];}}}return dp[n - 1][p[n - 1]];}
};

也可以用記憶化搜索實現：

class Solution {const int mod = 1000000007;
public:int numberOfPermutations(int n, vector<vector<int>>& re) {vector<int>p(n, -1);p[0] = 0;for(auto x : re){p[x[0]] = x[1];}if(p[0])return 0;int m = p[n - 1];vector<vector<int>> dp(n, vector<int>(m + 1, -1));auto dfs = [&] (auto&& dfs, int i, int j){if(i == 0){return 1;} if(dp[i][j] != -1)return dp[i][j];int & sum = dp[i][j];sum = 0;if(p[i - 1] == -1){for(int k = 0; k <= min(i, j); ++k){sum = (sum + dfs(dfs, i - 1, j - k)) % mod;}}else {if(j >= p[i - 1] && j <= i + p[i - 1]){sum = dfs(dfs, i - 1, p[i - 1]);}}return sum;};return dfs(dfs, n - 1, p[n - 1]);}
};

這樣寫的時間復雜度是O(n * m * min(n, m))，空間復雜度是O(n * m)

優化

我們可以發現對于無限制的那段$dp[i][j]$是一個連續的區間加法，可以用前綴和來優化枚舉k的過程，要注意下標寫對了

甚至還可以用滾動數組把空間降下來，這里懶得寫了

class Solution {const int mod = 1000000007;
public:int numberOfPermutations(int n, vector<vector<int>>& re) {vector<int>p(n, -1);for(auto x : re){p[x[0]] = x[1];}int m = p[n - 1];vector<vector<int>> dp(n, vector<int>(m + 1, 0));dp[0][0] = 1;for(int i = 1; i < n; ++i){int mx = p[i] == -1 ? m : p[i];if(p[i - 1] == -1){//無限制vector<int>pre(m+1, 0);pre[0] = dp[i - 1][0];for(int j = 1; j <= m; ++j)pre[j] = (pre[j - 1] + dp[i - 1][j])%mod;for(int j = 0; j <= mx; ++j){dp[i][j] = (pre[j] - (j - min(i, j) == 0 ? 0 : pre[j - min(i, j) - 1]) + mod) % mod;}}else{//有限制for(int j = p[i - 1]; j <= min(mx, p[i - 1] + i); ++j){dp[i][j] = dp[i - 1][p[i - 1]];}}}return dp[n - 1][p[n - 1]];}
};