3193. 统计逆序对的数目

题目描述：

给定一个长度为n的二维数组re，其中re[i] = [id_i, cnt_i]，求存在多少个全排列perm满足对所有的re[i]都有perm[0..id_i]恰好有 cnt_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]];
    }
};