2531 最大覆盖(区间)_嘘......的博客-程序员秘密_最大覆盖

技术标签: 51nod  

现在有 n 个位置 1…n。给q个区间,请你选出选q−2个,使得覆盖位置个数最大。
输入
第一行两个数n,q(3<=n,q<=5000)。
接下来q行,其中第i行两个数l[i],r[i],表示第i个区间能覆盖所有满足l[i]<=x<=r[i]的位置x。
输出
一个数表示最大值。
输入样例
4 3
1 1
2 2
3 4
输出样例
2
反方,求出两个区间覆盖最小值,减去
因为减,要注意是否去掉这个区间后该点不被其他区间包含

#include<bits/stdc++.h>
using namespace std;
struct node{
    
	int l,r;
}p[5010];
int v[5010],v1[5010],n,q,ans=0,maxn=0,t,t1;
int main()
{
    	
 ios::sync_with_stdio(false);
 cin>>n>>q;
 for(int i=1;i<=q;i++)
 {
    
 	cin>>p[i].l>>p[i].r;
 	for(int j=p[i].l;j<=p[i].r;j++)
 	{
    
 	 if(!v[j])
 	  ans++;	
	 v[j]++;
    }
 }
 for(int i=1;i<=q;i++)
 {
    
 	for(int j=i+1;j<=q;j++)
 	{
    
 	 t=0;
     memcpy(v1,v,sizeof(v));
	 for(int k=p[i].l;k<=p[i].r;k++) 
	  v1[k]--;
	 for(int k=p[j].l;k<=p[j].r;k++) 
	  v1[k]--;
	 for(int k=1;k<=n;k++) 
	  if(v1[k]<=0&&v[k]>0)
	   t++;	      
	 maxn=max(maxn,ans-t);	
	}
	if(maxn==ans)//不加超时 
	 break;
 }
 cout<<maxn;
 return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43540515/article/details/102527328

智能推荐

解决nginx报错:502 Bad Gateway以及504 Gateway Time-out问题_RealHarryWang的博客-程序员秘密

摘要wordpress及宝塔面板的基本环节,出现nginx错误:502 Bad Gateway 502 Bad Gateway以及504 Gateway Time-out 504 Gateway Time-out问题后的解决办法。 wordprss安装插件或者上传大文件时,总是时不时出现这个问题。错误——502 Bad Gateway 502 Bad ...

Mac 安装 CocoaPods 以及 Swift 使用 SocketIO 第三方库进行 Socket编程_留住这时光的博客-程序员秘密_mac 安装socket.io

文章目录CocoaPod 安装在项目中引入 SocketIO 第三方库CocoaPod 安装CocoaPods是iOS开发、macOS开发中的包依赖管理工具,类似于Java中的Maven,nodejs的npm。su root// 更新gemsudo gem update --systemsudo gem install -n /usr/local/bin cocoapods参考在项目中引入 SocketIO 第三方库首先进入项目根目录,使用快捷键 command + option +

react列表渲染_橙程橙的博客-程序员秘密_react渲染列表(要求样式)并且每一行前面需要添加一个序号,序号从1开始

1.react中的列表渲染注意使用以下代码的话,注意包的导入路径&lt;!DOCTYPE html&gt;&lt;html lang="en"&gt;&lt;head&gt; &lt;meta charset="UTF-8"&gt; &lt;title&gt;Document&lt;/title&gt; &lt;script src="./js/react.js"&gt;&lt...

如何更愉快地使用em_前端大全的博客-程序员秘密

(点击上方公众号,可快速关注)英文:Keith J.Grant  译文:Yuying Wuhttp://wuyuying.com/blog/archives/css-in...

win7+cpu+caffe ssd+python35+cmake安装编译_huangnachuan的博客-程序员秘密_python windows7 cmake

一、参考资料:https://blog.csdn.net/thecentry/article/details/90318360https://www.cnblogs.com/neo-T/p/ssd-caffe-vs2015.html二、准备工作:1.安装cmake,网上很多的版本,下载一个最新的即可;2.下载caffe-ssd,网上搜索了很多的资料,太多的来源了,不知道选哪个好,参考一个最近还在有维护的;下载路径为https://github.com/runhang/caffe-ssd-windo

随便推点

Hive面试题(持续更新)_听海的石头的博客-程序员秘密_hive处理数据时一般不对数据进行改写

1、Hive的架构2、Hive的特点数据存储位置Hive的数据存储在hdfs上,元数据可以存储在指定的地方比如mysql,PostgreSQL等。数据更新Hive处理数据时一般不对数据进行改写,因为它不支持行级别的增删操作,如果要进行更新数据,一般可以通过分区或者表直接覆盖。执行效率Hive 执行延迟较高。虽然在小数据量时传统数据库延迟更低,但是当数据规模大到超过传统数据库的处理能力的时候,Hive 的并行计算显然能体现出优势。数据规模Hive 支持大规模的数据计算,通常是PB级别的数

#2020寒假集训#C++STL-set代码笔记_薄荷糖·琳的博客-程序员秘密

#include&lt;stdio.h&gt;#include&lt;iostream&gt;#include&lt;bits/stdc++.h&gt;//万能头文件 #include&lt;set&gt;//set头文件using namespace std;int main(){ printf("\n"); set&lt;int&gt; s;//set自动去重升序 mult...

Swin Transformer实战目标检测:训练自己的数据集_bai666ai的博客-程序员秘密

课程链接:Swin Transformer实战目标检测:训练自己的数据集--计算机视觉视频教程-人工智能-CSDN程序员研修院Transformer发轫于NLP(自然语言处理),并跨界应用到CV(计算机视觉)领域。Swin Transformer是基于Transformer的计算机视觉骨干网,在图像分类、目标检测、实例分割、语义分割等多项下游CV应用中取得了SOTA的性能。该项工作也获得了ICCV 2021顶会最佳论文奖。本课程将手把手地教大家使用labelImg标注和使用Swin Transfo.

python 常用的世界坐标系互相转化_hr_net的博客-程序员秘密

from coord_convert.transform import wgs2gcj, wgs2bd, gcj2wgs, gcj2bd, bd2wgs, bd2gcj"""1.coord-convert库,pip install coord-convert2.wgs2gcj : convert WGS-84 to GCJ-02wgs2bd : convert WGS-84 to DB-09gcj2wgs : convert GCJ-02 to WGS-84gcj2bd : conv.

CF1369D TediousLee 题解(树形DP+递推)_PYL2077的博客-程序员秘密

题目链接个人认为是一道非常有意思的题,题意就不赘述了首先,要发现这题的做法,必须要先打表找规律。可以自己在纸上用手捏出 n≤6n\le 6n≤6 的数据经过打表后,我们可以发现下面这个规律:图稍微有点丑,见谅...

基于boosting和bagging算法预测离职员工_fudongxing5689的博客-程序员秘密

基于boosting和bagging算法预测离职员工数据介绍数据预览查看数据数据信息数据预处理描述统计变量相关性连续变量相关性连续变量与因变量相关性数据分析描述性分析工作是否有失误与离职的关系最近五年是否被提升与离职的关系职位与离职的关系薪水与离职的关系运用boosting算法和bagging算法预测可能离职的员工结论数据介绍HR_comma_sep是从Kaggle下载的关于现有员工是否已经离职的数据集,共包含10个特征,有员工的工作满意度,员工所在岗位以及员工是否离职等等特征,该数据集共14999个样

推荐文章

热门文章

相关标签