Codevs 3012 线段覆盖 4

2023-12-25 16:18

文章标签 覆盖线段 codevs 3012

本文主要是介绍Codevs 3012 线段覆盖 4，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3012 线段覆盖 4
时间限制: 1 s
空间限制: 64000 KB
题目等级 : 黄金 Gold
题目描述 Description
数轴上有n条线段，线段的两端都是整数坐标，坐标范围在0~1000000，每条线段有一个价值，请从n条线段中挑出若干条线段，使得这些线段两两不覆盖（端点可以重合）且线段价值之和最大。
输入描述 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
n <= 1000000
0<=ai,bi<=1000000
0<=ci<=1000000
数据输出建议使用long long类型（Pascal为int64或者qword类型）
分类标签 Tags
二分法动态规划序列型DP

/*
DP.
f[i]表示选前i个线段的最优值.
然后DP选不选该线段.
我们保证f值单调. 
然后我们从n^2优化到nlogn.
如果从前边转移的话.
按照右端点排序.
找一个合法最近的线段更新.
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXN 1000001
#define LL long long
using namespace std;
LL f[MAXN],n,tot;
struct data{LL x,y,z;}s[MAXN];
LL read()
{LL x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f;
}
bool cmp(const data &x,const data &y)
{return x.y<y.y;
}
LL erfen(LL l,LL p)
{LL mid,ans,r=p-1;while(l<=r){mid=(l+r)>>1;if(s[mid].y<=s[p].x)ans=mid,l=mid+1;else r=mid-1;}return ans;
}
int main()
{LL x,y,z;n=read();for(int i=1;i<=n;i++)s[i].x=read(),s[i].y=read(),s[i].z=read();sort(s+1,s+n+1,cmp);for(int i=1;i<=n;i++)f[i]=max(f[i-1],f[erfen(0,i)]+s[i].z),tot=max(tot,f[i]);printf("%lld",tot);return 0;
}

/*
按照左端点排序.
从后面更新状态. 
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXN 1000001
#define LL long long
using namespace std;
LL f[MAXN],n,tot;
struct data{LL x,y,z;}s[MAXN];
LL read()
{LL x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f;
}
bool cmp(const data &x,const data &y)
{return x.x<y.x;
}
LL erfen(LL p)
{LL mid,ans,l=p+1,r=n+1;while(l<=r){mid=(l+r)>>1;if(s[mid].x>=s[p].y)ans=mid,r=mid-1;else l=mid+1;}return ans;
}
int main()
{LL x,y,z;n=read();for(int i=1;i<=n;i++)s[i].x=read(),s[i].y=read(),s[i].z=read();sort(s+1,s+n+1,cmp);for(int i=n;i>=1;i--)f[i]=max(f[i+1],f[erfen(i)]+s[i].z),tot=max(tot,f[i]);printf("%lld",tot);return 0;
}