【BZOJ2034】最大收益(贪心)
最大 贪心 收益
2023-09-11 14:14:40 时间
【BZOJ2034】最大收益(贪心)
题面
题解
首先显然让价值越大的占用一个时刻一定更优。
所以把所有东西按照价值排序之后来处理,那么显然就是把前面的全部放好之后,考虑来放当前这个东西,如果能够放下那么就放,否则直接丢掉。
考虑如何检查是否能下放。
首先缩小区间的规模,对于每个位置,找到从他们的左端点开始,往右第一个未被标记的点标记,最后只有被标记的点才可能出现在匹配中。
那么记录每个点的匹配位置,然后从左往右考虑所有可以的匹配位置,如果当前位置没有匹配,则直接匹配。
否则如果当前位置匹配的东西的\([l,r]\)的\(r\)比这段区间的\(r\)大,则尝试能否匹配本来放的东西(因为它的\(r\)更大,更可能在后面找到一个匹配),如果不行则不行,否则则修改匹配有解。
这样子最多检查\(n\)个元素的匹配,而只需要加入\(n\)次,所以复杂度\(O(n^2)\)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 5050
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,p[MAX],book[MAX];ll ans;
struct Node{int l,r,v,p;}a[MAX];
bool cmpv(Node a,Node b){return a.v>b.v;}
bool cmpl(Node a,Node b){return a.l<b.l;}
bool check(int x,int pos)
{
if(p[pos]>a[x].r)return false;
if(!book[pos]){book[pos]=x;return true;}
if(a[book[pos]].r<=a[x].r)return check(x,pos+1);
else if(check(book[pos],pos+1)){book[pos]=x;return true;}
return false;
}
int main()
{
n=read();
for(int i=1;i<=n;++i)a[i].l=read(),a[i].r=read(),a[i].v=read();
sort(&a[1],&a[n+1],cmpl);
for(int i=1;i<=n;++i)p[i]=max(p[i-1]+1,a[i].l);
a[1].p=1;
for(int i=2;i<=n;++i)
{
a[i].p=a[i-1].p;
while(p[a[i].p]<a[i].l&&a[i].p<n)++a[i].p;
}
sort(&a[1],&a[n+1],cmpv);
for(int i=1;i<=n;++i)if(check(i,a[i].p))ans+=a[i].v;
printf("%lld\n",ans);
return 0;
}
相关文章
- hdu4846 最大子正方形(dp)
- POJ1466 最大点权独立集
- 【华为OD机试真题 python】最大利润【2022 Q4 | 100分】
- 单机最大tcp连接数
- 【BZOJ4205】卡牌配对 最大流
- LeetCode高频题84. 柱状图中最大的矩形,单调栈求位置i左边右边距离i最近且比i位置小的位置,然后结算面积
- Leetcode 85.最大矩形(困难)
- postgresql数据库, 查看表的每一个字段中数据最大长度是多少
- 《模式识别》学习笔记(十七)含拒绝判断的最小损失准则,最小最大损失准则
- 贪心算法之拼接最大数字问题
- BZOJ 1059 [ZJOI2007]矩阵游戏 (二分图最大匹配)
- 张钹院士:场景是当前AI产业化最大问题
- 还在用Hadoop么?Hadoop服务器造成5PB数据泄露,中国、美国受波及最大!
- 源码推荐(7.17):不规则按钮类似于遥控器按钮,一个可以最大程度简化PageView与TabView切换的第三方框架
- 智能家居物联网化将成为AWE大会最大看点
- 【华为OD机试真题 java、python、c++、JsNode】最大利润、贪心的商人(100%通过+复盘思路)
- 【历史上的今天】11 月 28 日:中国顶级域名 CN 被注册;上世纪最大的论坛诞生;首个 Fortran 程序开发者逝世
- 苏美达辉伦获印度市场最大光伏组件订单
- 分析师观点:WiFi将成为5G技术的最大竞争对手
- 从全球最大光伏展看中国光伏行业:火爆的背后是什么?
- [LeetCode] Maximum Sum of 3 Non-Overlapping Subarrays 三个非重叠子数组的最大和