当前位置: 首页 > news >正文

牛客练习赛122

D:圆

正着求删除的最小代价不好做,采用逆向思维,求选择一些不相交的线段使得构成一个圆的代价尽量大,最后答案就是所有线段权值之和减去最大代价。

那么如何求这个最大代价呢?显然区间DP

老套路:破环成链,枚举区间长度 len ,枚举区间左端点 i 和右端点 j

很明显没有线段长度为1,故len从2开始

具体的

线段的操作和点的相似但又不完全相同具体看代码即可。

1:不选择以左端点的线段,f[i][j]=f[i+1][j];

2、选择以为左端点的线段。枚举左端点 所能到达的右端点 v,权值为 w,那么当前的答案

由 区间  [i+1,k-1]  的答案加上 区间  [k +1[j]  的答案加上线段  [ i, v ] 的权值构成,即

 f[i][j]=f[i+1][v-1]+f[v+1][j]+val(i,v);

int n, m;
int f[M][M]; // f[i][j]  区间i到j不相交边的最大价值
vector<PII> g[N];
void solve()
{cin >> n >> m;int s = 0;for (int i = 1; i <= m; i++){int x, y, w;cin >> x >> y >> w;if (x > y)swap(x, y);g[x].pb({y, w});g[y].pb({x + n, w});s += w;}for (int len = 2; len <= 2 * n; len++){for (int i = 1; i + len - 1 <= 2 * n; i++){int j = i + len - 1;f[i][j] = f[i + 1][j]; // 不选择以i为左端点的线段for (auto ed : g[i])   // 选择以i为左端点的线段{int v = ed.xx, w = ed.yy;if (v > j) // 已经越过右端点了continue;if (v - 1 > i + 1) //区间端点,不能相同w += f[i + 1][v - 1];if (j > v + 1)w += f[v + 1][j];f[i][j] = max(f[i][j], w);}}}int tmp = 0;for (int i = 1; i <= n; i++)tmp = max(tmp, f[i][i + n - 1]);s = s - tmp;cout << s << endl;
}

类似的题目

Codeforces Round 661 (Div. 3)

F. Yet Another Segments Subset

两个题目非常相似但是又不完全相同。

本题的数据显然如果直接区间dp会超时,但是n却是很小我们想能不能进行离散化。

本题的相交比较上一题有点不同,不同在包含的时候端点可以相交,而不包含时端点不可相交。

很明显,离散化候不同区间值被拉近了距离,但是不相交得还是不相交,所以本题可以离散化。(具体题目具体分析,有的题目可能会有坑)

状态表示:f[i][j]  表示区间  [i,j]  里面满足题意得最大区间数量。

然后我们就想一下转移方程:

具体的还是区间DP的过程,枚举区间长度 len ,枚举区间左端点 i 和右端点 j

我们还是以选不选以 i 为左端点的区间,

1:不选  f[i][j]=f[i+1][j];

2:选  f[i][j]=max(f[i][j],f[i][k],f[k+1][j]);(k<j)

我们看第二个方程,很明显就是我们上面说的;

即只有完全包含端点才可以相同;

我们还要注意一种情况那就是区间恰好等于 [i,j] ,这种情况由于(k<j) ,被跳过了

所以最后加上个数即可完成。

int n;
PII p[N];
vector<int> g[N];
void solve()
{vector<int> t;cin >> n;for (int i = 1; i <= n; i++){int l, r;cin >> l >> r;p[i] = {l, r};t.pb(l);t.pb(r);}sort(t.begin(), t.end());t.erase(unique(t.begin(), t.end()), t.end());for (int i = 1; i <= n; i++){int x = lower_bound(t.begin(), t.end(), p[i].xx) - t.begin() + 1;int y = lower_bound(t.begin(), t.end(), p[i].yy) - t.begin() + 1;g[x].pb(y);}int m = t.size();vector<vector<int>> f(m + 10, vector<int>(m + 10));for (int len = 1; len <= m; len++){for (int i = 1; i + len - 1 <= m; i++){int j = i + len - 1;f[i][j] = f[i + 1][j];int cnt = 0;for (auto ed : g[i]){int v = ed;if (v == j)cnt++;if (v < j)f[i][j] = max(f[i][v] + f[v + 1][j], f[i][j]);}f[i][j] += cnt;}}cout << f[1][m] << endl;for (int i = 0; i <= m + 1; i++)g[i].clear();
}

相关文章:

牛客练习赛122

D:圆 正着求删除的最小代价不好做&#xff0c;采用逆向思维&#xff0c;求选择一些不相交的线段使得构成一个圆的代价尽量大&#xff0c;最后答案就是所有线段权值之和减去最大代价。 那么如何求这个最大代价呢&#xff1f;显然区间DP 老套路&#xff1a;破环成链&#xff0…...

软考复习调整策略和学习计划!

根据软考办发布的最新通知&#xff0c;在群里引起了热烈讨论的是2024年度计算机技术与软件专业技术资格&#xff08;水平&#xff09;考试的安排。其中&#xff0c;信息系统项目管理师&#xff08;简称高项&#xff09;的考试次数从每年两次减少到只有5月份进行&#xff0c;而系…...

1小时网络安全事件报告要求,持安零信任如何帮助用户应急响应?

12月8日&#xff0c;国家网信办起草发布了《网络安全事件报告管理办法&#xff08;征求意见稿&#xff09;》&#xff08;以下简称“办法”&#xff09;。拟规定运营者在发生网络安全事件时应当及时启动应急预案进行处置。 1小时报告 按照《网络安全事件分级指南》&#xff0c…...

mysql使用连接池

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、mysql连接池&#xff1f;二、使用步骤1.引入库 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 例如&#xff1a; 提示&#xff1a…...

06. Nginx进阶-Nginx代理服务

proxy代理功能 正向代理 什么是正向代理&#xff1f; 正向代理&#xff08;forward proxy&#xff09;&#xff0c;一个位于客户端和原始服务器之间的服务器。 工作原理 为了从原始服务器获取内容&#xff0c;客户端向代理发送一个请求并指定目标&#xff08;即原始服务器…...

STM32 (1)

1.基本信息 stm32是由ST公司生产的一种32位微控制器&#xff08;单片机&#xff09;。 1.1 各种型号 stm32是32位单片机的总称&#xff0c;有多种不同的系列。 32即用32个比特位表示一个地址&#xff0c;寻址范围&#xff1a;0x00000000 --0xffffffff (4GB) 1.2 存储密度 …...

Spring初始(相关基础知识和概述)

Spring初始&#xff08;相关基础知识和概述&#xff09; 一、Spring相关基础知识&#xff08;引入Spring&#xff09;1.开闭原则OCP2.依赖倒置原则DIP3.控制反转IoC 二、Spring概述1.Spring 8大模块2.Spring特点2.Spring的常用jar文件 一、Spring相关基础知识&#xff08;引入S…...

【Swift 周报 第四十七期

文章目录 前言新闻和社区苹果财报来袭&#xff1a;营收有望再创新高 巴克莱或将惨遭打脸&#xff1f;Apple 为在全球范围内提供迷你 App 和游戏访问的流媒体游戏服务和 App 发布新选项Swift Student Challenge 将于 2 月 5 日开放申请 提案通过的提案正在审查的提案 Swift论坛推…...

STM32(16)使用串口向电脑发送数据

发送字节 发送数组 发送字符和字符串 字符&#xff1a; 字符串&#xff1a; 字符串在电脑中以字符数组的形式存储...

利用大模型技术进行测试用例推荐如何实现

利用大模型技术进行测试用例推荐&#xff0c;可以通过以下步骤实现&#xff1a; 确定目标和需求&#xff1a;明确测试用例推荐的目标和需求&#xff0c;例如推荐哪些类型的测试用例、推荐的数量、推荐的准确率等。 收集数据&#xff1a;收集历史测试用例、需求文档、设计文档等…...

Linux学习:初识Linux

目录 1. 引子&#xff1a;1.1 简述&#xff1a;操作系统1.2 学习工具 2. Linux操作系统中的一些基础概念与指令2.1 简单指令2.2 ls指令与文件2.3 cd指令与目录2.4 文件目录的新建与删除指令2.5 补充指令1&#xff1a;2.6 文件编辑与拷贝剪切2.7 文件的查看2.8 时间相关指令2.9 …...

Python CGI编程错误汇总

文章目录 1 前言2 测试文件3 问题总结 1 前言 在学习Python CGI编程时&#xff0c;运行起来总是有各种各样的问题&#xff0c;故将问题进行总结&#xff0c;以便新接触Python的童鞋能少走弯路 以下均为本人遇到对应报错的解决方案&#xff0c;可能存在其他问题但报错相同的情况…...

第十三届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组 统计子矩阵

#include<iostream> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue>using namespace std;int cnt,temp; int n,m,K; int a[505][505]; int pre[505][505];//二维前缀和void sol() {cin>>…...

计算机网络实验 基于ENSP的协议分析

实验二 基于eNSP的协议分析 一、实验目的&#xff1a; 1&#xff09;熟悉VRP的基本操作命令 2&#xff09;掌握ARP协议的基本工作原理 3&#xff09;掌握IP协议的基本工作原理 4&#xff09;掌握ICMP协议的基本工作原理 二、实验内容&#xff1a; 1、场景1&#xff1a;两台PC机…...

Java实现手机库存管理

一、实验任务 编写一个程序&#xff0c;模拟库存管理系统。该系统主要包括系统首页、商品入库、商品显示和删除商品功能。每个功能的具体要求如下&#xff1a; 1.系统的首页&#xff1a;用于显示系统所有的操作&#xff0c;并且可以选择使用某一个功能。 2.商品入库功能&…...

单片机入门:LED数码管

LED数码管 LED数码管&#xff1a;由多个发光二极管封装在一起组成的“8”字型的器件。如下图所示&#xff1a; 数码管引脚定义 一位数码管 内部由八个LED组成。器件有十个引脚。 对于数码管内的8个LED有共阴和共阳两种连接方法。 共阴&#xff1a;将8个LED的阴极都连接到一…...

软考信息系统项目管理师零基础怎么学习?

软考考信息系统项目管理师&#xff0c;零基础怎么入手高项&#xff1f; 要我说对于没有基础的人群来说零基础考信息系统项目管理师还是有一定的难度的&#xff0c;难就难在需要时间去了解基础&#xff0c;而相对于系统分析师、系统构架设计师、网络规划设计师、系统规划与管理…...

【轮式平衡机器人】——TMS320F28069片内外设之Timer_IT(补:CCS程序烧录方法)

引入 Timer_IT 指的是 TMS320F28069 的定时器中断功能。在微控制器或数字信号控制器中&#xff0c;定时器是一个非常重要的外设&#xff0c;它可以用来产生固定时间间隔的中断&#xff0c;或者用来精确计算时间。 Timer_IT 的主要特点如下&#xff1a; 定时功能&#xff1a;…...

安装Proxmox VE虚拟机平台

PVE是专业的虚拟机平台&#xff0c;可以利用它安装操作系统&#xff0c;如&#xff1a;Win、Linux、Mac、群晖等。 1. 下载镜像 访问PVE官网&#xff0c;下载最新的PVE镜像。 https://www.proxmox.com/en/downloads 2. 下载balenaEtcher balenaEtcher用于将镜像文件&#…...

后端项目访问不了

问题&#xff1a; 后端启动不了&#xff0c;无法访问网站 原因&#xff1a; 1.防火墙没有关 2.有缓存 3、项目没有启动 4、docker没有启动 解决&#xff1a; 先查看进程&#xff1a;docker ps&#xff0c;必须有三个 详细查看&#xff1a;docker ps -a exited代表没有开启…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...