线段覆盖 2(序列DP)
2024-08-21 10:49:37
Code vs 3027 线段覆盖 2
题目描述 Description
数轴上有n条线段,线段的两端都是整数坐标,坐标范围在0~1000000,每条线段有一个价值,请从n条线段中挑出若干条线段,使得这些线段两两不覆盖(端点可以重合)且线段价值之和最大。
n<=1000
输入描述 Input Description
第一行一个整数n,表示有多少条线段。
接下来n行每行三个整数, ai bi ci,分别代表第i条线段的左端点ai,右端点bi(保证左端点<右端点)和价值ci。
输出描述 Output Description
输出能够获得的最大价值
样例输入 Sample Input
3
1 2 1
2 3 2
1 3 4
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
数据范围
对于40%的数据,n≤10;
对于100%的数据,n≤1000;
0<=ai,bi<=1000000
0<=ci<=1000000
//想了很久,dp[i] 意思是起点为 0 终点为线段 i 的右端点的区间的可达的最大价值,所以转移方程是 , 具体点,关联到每条边
dp [i] = max ( max ( dp [ 0 --- i-1 ) + edge[i].v , dp [ i ] )
所有线段先按右端升序排好序,这样比较有条理,不会乱,再来说上面三个条件的意思
第一个前面的不冲突的最大价值加上这条线段的价值,也就是与这条线段共同覆盖可以达到的价值
第二个是不使用这条线段就有的价值
然后就很简单了。。。这样很快,有个细节要注意。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; struct Edge
{
int l,r;
int v;
bool operator <(const Edge & b)const
{return r<b.r;}
}edge[];
int dp[]; int main()
{
int n;
scanf("%d",&n);
for(int i=;i<n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edge[i].l=min(a,b);
edge[i].r=max(a,b);
edge[i].v=c;
}
sort(edge,edge+n);
for (int i=;i<n;i++)
{
for (int j=i-;j>=;j--)
{
if (edge[j].r<=edge[i].l)
dp[i]=max(dp[j]+edge[i].v,dp[i]);
}
dp[i]=max(edge[i].v,dp[i]);
}
int ans=;
for (int i=;i<n;i++)
ans=max(ans,dp[i]);
cout<<ans<<endl;
return ;
}
最新文章
- 对于挑战书上的很久之前都看不懂的DP看懂的突破
- 优化SQLServer——表和分区索引
- ajaxfileupload.js
- HDU5437 Alisha’s Party 优先队列
- HQL: Hibernate查询语言
- 64位调试器花费的时间比预期的要长(A 64-bit debugging operation is taking longer than expected)
- Minimum Window Substring @LeetCode
- python3使用smtplib发电子邮件
- 【转】iOS 开发者必不可少的 75 个工具
- UVa 793 - Network Connections
- 冲刺NO.8
- Docker部署脚本
- NOIP2012提高组day2 T2借教室
- 【Spark篇】---Spark中广播变量和累加器
- SQL SEVER 时间格式转换
- AVL树平衡旋转详解
- 4-Four-Seeing hands
- 四则运算3+PSP
- Linux 操作日志
- ASP.NET MVC编程——路由
热门文章
- EarlyZ disable( earlyz失效
- 格式化HDFS
- ASP.NET MVC学习---(三)EF简单增删改查
- 右键添加";在此处打开命令窗口";菜单
- Tomcat 高性能实现关键点
- 12. 改变JDK编译版本【从零开始学Spring Boot】
- SpringMVC传值(对象或字符串)给前台js
- sql CHARINDEX() 与 PATINDEX() LEN() substring() COLLATE RAISERROR
- ASP.NET CORE RAZOR :将搜索添加到 Razor 页面应用
- svn hooks使用