【匹配线段问题】
问题:
如下图所示。图中有两行正整数,每行中有若干个正整数。如果第一行的某个数r与第二行的某个数相同,这样就可以在这两个正整数之间划一条线,并称之为r-匹配线段。下图中存在3-匹配线段和2-匹配线段。

请编写完整程序,求最大的匹配线段数量,并使得这些匹配线段满足如下条件:
- 每一个a-匹配线段必须与另一个b-匹配线段相交,且a不等于b.
- 任何两个匹配线段不能从同一个整数出发。如下图中3-匹配线段是不合法的匹配线段。

不满足上述两个条件的匹配线段则不能称之为匹配线段,不计入匹配线段的数量。例如有两行整数分别如下,则该例中其匹配线段的数量为6.
1 3 1 3 1 3
3 1 3 1 3 1
下面的匹配线段数量则为0。因为虽然最多可划4条匹配线段,但不满足这其中2条匹配线段相交且a-匹配线段不等于b匹配线段的条件,因此其匹配线段的数量为0.
1 1 3 3
1 1 3 3
思路:
回溯法。
第n层顺序考虑第1行的第n个正整数与第2行的某个正整数进行匹配,匹配后需要在一个一维向量中标记,代表下次不可以参与匹配。
当达到深度时,分支被目标函数截断,进行匹配线段的计算(也要找匹配,找到一定记得退出循环),那么将匹配线段数目与最优值作比较,更新最优值。
难点:匹配线段的计算函数,匹配对的存储。
代码:
#include<bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
int n;
int first[110];
int second[110];
int sign[110];
int best;int cal(int cnt, PII duple[])
{int result = 0;int sign[cnt+1] = {0};for(int i = 1; i <= cnt; i++){if(sign[i]) continue;for(int j = 1; j <= cnt; j++){if(first[duple[i].first] == first[duple[j].first]) continue;if((duple[i].first - duple[j].first) * (duple[i].second - duple[j].second) < 0){sign[i] = 1, result += 1;if(!sign[j]) sign[j] = 1, result += 1;break;}}}return result;
}
void dfs(int k, int cnt, PII duple[])
{if(k > n){int this_time = cal(cnt, duple);if(this_time > best) best = this_time;}for(int i = 1; i <= n; i++){if(second[i] != first[k]) continue;if(sign[i]) continue;sign[i] = 1;duple[cnt+1] = {k, i};dfs(k+1, cnt+1, duple);duple[cnt+1] = {}; sign[i] = 0;}
}
int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> first[i];}for(int i = 1; i <= n; i++){cin >> second[i];}PII duple[110];dfs(1, 0, duple);cout << best << endl;return 0;
}
相关文章:
【匹配线段问题】
问题: 如下图所示。图中有两行正整数,每行中有若干个正整数。如果第一行的某个数r与第二行的某个数相同,这样就可以在这两个正整数之间划一条线,并称之为r-匹配线段。下图中存在3-匹配线段和2-匹配线段。 请编写完整程序…...
vue中$bus.$emit和$bus.$on的用法温故
$bus. $emit、 $bus. $on 用于非父子组件之间通信 1、在main.js中注册 Vue.prototype.$bus new Vue();new Vue({render: h > h(App),router,store }).$mount(#app)2、在需要发送信息的组件中,发送事件 this.$bus.$emit("method",params);…...
【JavaScript脚本宇宙】优化你的React项目:探索表单库的世界
React表单库解析:特性,使用方法和使用场景 前言 在现代的web开发中,表单是Web应用程序的核心组成部分之一。为了助力开发者更快捷、高效地处理表单状态和验证等问题,本文将介绍六种不同的React表单库,包括它们的特性…...
kvm虚拟化
虚拟化是一种资源管理技术,是将计算机的各种资源,如服务器,网络,内存及存储等,以抽象,转换后呈现出来,打破物理设备结构见的不可切割的障碍,使用户可以比原来的架构更好的方式来应用…...
算法训练营第五十天 | LeetCode 198 打家劫舍、LeetCode 213 打家劫舍II、LeetCode 337 打家劫舍III
LeetCode 198 打家劫舍 代码如下: class Solution { public:int rob(vector<int>& nums) {vector<int> dp(nums.size() 1, 0);dp[1] nums[0];for (int i 2; i < nums.size(); i) {dp[i] max(dp[i - 1] ,dp[i - 2] nums[i - 1]);}return dp…...
linux学习:进程通信 管道
目录 例子1 父进程向子进程发送一条消息,子进程读取这条消息 例子2 mkfifo 函数创建一个命名管道 例子3 mkfifo 函数创建一个命名管道处理可能出现的错误 例子4 管道文件是否已存在 例子5 除了“文件已存在”进行处理 例子6 创建一个命名管道&…...
重大变化,2024软考!
根据官方发布的2024年度计算机技术与软件专业技术资格(水平)考试安排,2024年软考上、下半年开考科目有着巨大变化,我为大家整理了相关信息,大家可以看看! 🎯2024年上半年:5月25日&am…...
DRIVEN|15分的CNN+LightGBM怎么做特征分类,适用于转录组
说在前面 今天分享一篇做深度学习模型的文章,这是一篇软硬结合的研究,排除转换实体产品,我们做生信基础研究的可以学习模仿这个算法,适用且不局限于临床资料,转录组数据,GWAS数据。 今天给大家分享的一篇文…...
react 怎样配置ant design Pro 路由?
Ant Design Pro 是基于 umi 和 dva 的框架,umi 已经预置了路由功能,只需要在 config/router.config.js 中添加路由信息即可。 例如,假设你需要为 HelloWorld 组件创建一个路由,你可以将以下代码添加到 config/router.config.js 中…...
DBSCAN 算法【python,机器学习,算法】
DBSCAN 即 Density of Based Spatial Clustering of Applications with Noise,带噪声的基于空间密度聚类算法。 算法步骤: 初始化: 首先,为每个数据点分配一个初始聚类标签,这里设为0,表示该点尚未被分配…...
MySQL之查询性能优化(六)
查询性能优化 查询优化器 9.等值传播 如果两个列的值通过等式关联,那么MySQL能够把其中一个列的WHERE条件传递到另一列上。例如,我们看下面的查询: mysql> SELECT film.film_id FROM film-> INNER JOIN film_actor USING(film_id)-> WHERE f…...
生成树协议STP(Spanning Tree Protocol)
为了提高网络可靠性,交换网络中通常会使用冗余链路。然而,冗余链路会给交换网络带来环路风险,并导致广播风暴以及MAC地址表不稳定等问题,进而会影响到用户的通信质量。生成树协议STP(Spanning Tree Protocol࿰…...
03-3.1.1 栈的基本概念
👋 Hi, I’m Beast Cheng👀 I’m interested in photography, hiking, landscape…🌱 I’m currently learning python, javascript, kotlin…📫 How to reach me --> 458290771qq.com 喜欢《数据结构》部分笔记的小伙伴可以订…...
排序算法集合
1. 冒泡排序 排序的过程分为多趟,在每一趟中,从前向后遍历数组的无序部分,通过交换相邻两数位置的方式,将无序元素中最大的元素移动到无序部分的末尾(第一趟中,将最大的元素移动到数组倒数第一的位置&…...
pdf文件太大如何变小,苹果电脑压缩pdf文件大小工具软件
压缩PDF文件是我们在日常办公和学习中经常会遇到的需求。PDF文件由于其跨平台、保持格式不变的特点,被广泛应用于各种场合。然而,有时候我们收到的PDF文件可能过大,不便于传输和存储,这时候就需要对PDF文件进行压缩。下面…...
vite项目打包,内存溢出
解决方案: "build1": "node --max-old-space-size8096 ./node_modules/vite/bin/vite.js build", 人工智能学习网站 https://chat.xutongbao.top...
Matlab解决施密特正交规范化矩阵(代码开源)
#最近在学习matlab,刚好和线代论文重合了 于是心血来潮用matlab建了一个模型来解决施密特正交规范化矩阵。 我们知道这个正交化矩阵挺公式化的,一般公式化的内容我们都可以用计算机来进行操作,节约我们人工的时间。 我们首先把矩阵导入进去…...
自养号测评助力:如何打造沃尔玛爆款?
沃尔玛,作为全球零售业的领军者,其平台为卖家们提供了一个巨大的商业舞台。然而,在这个竞争激烈的舞台上,如何迅速且有效地提升销量,成为了卖家们必须面对的重大挑战。 在探讨沃尔玛平台销量提升的策略时,我…...
C语言编译与链接
C语言编译与链接 目录 C语言编译与链接 一、概述 二、编译过程 三、链接过程...
电子电器架构 --- 智能座舱技术分类
电子电器架构 — 智能座舱技术分类 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...
软件工程 期末复习
瀑布模型:计划 螺旋模型:风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合:模块内部功能紧密 模块之间依赖程度小 高内聚:指的是一个模块内部的功能应该紧密相关。换句话说,一个模块应当只实现单一的功能…...
企业大模型服务合规指南:深度解析备案与登记制度
伴随AI技术的爆炸式发展,尤其是大模型(LLM)在各行各业的深度应用和整合,企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者,还是积极拥抱AI转型的传统企业,在面向公众…...
Linux安全加固:从攻防视角构建系统免疫
Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...
