首页 > 其他分享 >3193. 统计逆序对的数目

3193. 统计逆序对的数目

时间:2024-11-07 08:51:32浏览次数:3  
标签:return int res req dfs vector 3193 数目 逆序

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;
};

标签:return,int,res,req,dfs,vector,3193,数目,逆序
From: https://blog.csdn.net/weixin_45256307/article/details/143584843

相关文章

  • 逆序乘积式
    【问题描述】若两个正整数的乘积,等于两正整数各自逆序后的乘积,则称其为逆序乘积式。编写程序读入两个正整数,然后判断这两个正整数能否构成逆序乘积式。假设两个正整数的乘积不会超过int数据类型的表示范围。【输入形式】从控制台输入以一个空格分隔的两个正整数。【输出形......
  • C++ 逆序乘积式
     题目描述【问题描述】若两个正整数的乘积,等于两正整数各自逆序后的乘积,则称其为逆序乘积式。编写程序读入两个正整数,然后判断这两个正整数能否构成逆序乘积式。假设两个正整数的乘积不会超过int数据类型的表示范围。【输入形式】从控制台输入以一个空格分隔的两个正整数......
  • 2024-11-03:得到更多分数的最少关卡数目。用go语言,Alice 和 Bob 正在进行一个有 n 个关
    2024-11-03:得到更多分数的最少关卡数目。用go语言,Alice和Bob正在进行一个有n个关卡的游戏,其中每个关卡要么是困难模式(possible[i]==0),要么是简单模式(possible[i]==1)。玩家在游戏中获得分数的规则如下:通过简单模式的关卡可得1分,而遇到困难模式的关卡将扣除1分。Alice从......
  • xtu oj 逆序数(小数据) //冒泡排序
    题目描述给你一个序列x1,x2,…,xn,如果数对<xi,xj>,其中i<j,而xi>xj我们称之为逆序数对。一个序列的逆序数对的数目,称为这个序列的逆序数。比如说序列312,逆序数对为<3,1>和<3,2>,所以这个序列的逆序数为2。现在给你一个数字序列,请求其逆序数。输入每个样例为两行......
  • 《练习题011:阶乘-递归-反向输出-排序-逆序(共9种)》
    《目录》01:阶乘求和02:递归求阶乘03:递归输出04:反向输出05:反向输出II06:设置输出颜色07:算素数08:排序09:逆序列表01:阶乘求和题目求1+2!+3!+…+20!的和。程序分析1+2!+3!+…+20!=1+2(1+3(1+4(…20(1))))res=1foriinrange(20,1,-1):res=i*res+1......
  • 2024-10-23-leetcode每日一题-构成整天的下标对数目 II
    题目描述给你一个整数数组 hours,表示以 小时 为单位的时间,返回一个整数,表示满足 i<j 且 hours[i]+hours[j] 构成 整天 的下标对 i, j 的数目。整天 定义为时间持续时间是24小时的 整数倍 。例如,1天是24小时,2天是48小时,3天是72小时,以此类推。......
  • 逆序对的数量
    #include<iostream>usingnamespacestd;intnum[100010],temp[100010];longlongcount(intl,intr){if(l>=r)return0;longlongsum=0;intmid=(l+r)>>1;sum+=count(l,mid);sum+=count(mid+......
  • c++ 构成整天的下标对数目 leetcode
    目录一、leetcode3184.构成 整天 的下标对数目I1.问题描述 2.方法:暴力穷举二、leetcode3185.构成 整天 的下标对数目II1.问题描述2.方法:哈希表一、leetcode3184.构成 整天 的下标对数目I1.问题描述给你一个整数数组 hours,表示以 小时 为单位的时间,返......
  • Leetcode刷题Python之3185.构成整天的下标对数目II
    提示:直接暴力求解会超过执行时间,因此要考虑其他方法降低复杂度。文章目录问题描述一、示例:二、解题思路1.找余数2.利用哈希表存储余数3.逐步统计配对数代码实现解释代码复杂度分析问题描述给定一个整数数组hours,表示时间,以小时为单位。我们需要找到数组中满......
  • LeetCode|3185. 构成整天的下标对数目 II(day21)
    作者:MJ昊博客:掘金、CSDN等公众号:程序猿的编程之路今天是昊的算法之路第21天,今天分享的是LeetCode第3185题构成整天的下标对数目II的解题思路。这是一道中等难度的题目,主要考察如何高效地统计两个元素之和为24的倍数的下标对,通过优化的算法减少时间复杂度。题目描......