当前位置：首页 > article >正文

3193. 统计逆序对的数目

article 2024/11/9 1:22:10

3193. 统计逆序对的数目

题目链接：3193. 统计逆序对的数目

代码如下：

class Solution 
{
public:
	int numberOfPermutations(int n, vector<vector<int>>& requirements) 
	{
		vector<int> req(n, -1);
		req[0] = 0;
		for (auto& p : requirements)
		{
			req[p[0]] = p[1];
		}
		if (req[0])
		{
			return 0;
		}

		int m = ranges::max(req);
		vector<vector<int>> memo(n, vector<int>(m + 1, -1));//-1表示没有计算过
		auto dfs = [&](auto&& dfs, int i, int j)->int
			{
				if (i == 0)
				{
					return 1;
				}
				int& res = memo[i][j];//注意这里是引用
				if (res != -1)//之前计算过
				{
					return res;
				}
				res = 0;
				if (int r = req[i - 1]; r >= 0)
				{
					if (j >= r && j - i <= r)
					{
						res = dfs(dfs, i - 1, r);
					}
				}
				else
				{
					for (int k = 0; k <= min(i, j); k++)
					{
						res=(res+dfs(dfs,i-1,j-k))%MOD;
					}
				}
				return res;
			};
		return dfs(dfs, n - 1, req[n - 1]);
	}

private:
	const int MOD = 1'000'000'007;
};