当前位置:网站首页>[training Day1] maximum benefit [discretization] [greed]
[training Day1] maximum benefit [discretization] [greed]
2022-07-18 08:49:00 【VL——MOESR】

The main idea of the topic :
give n A mission , Every task has value , And it has to be in s[i] To t[i] At a certain time within the time , Ask the greatest value
Ideas :
We first found out , At most n Time selected , So so many moments are useless
We discretize it directly
How to discretize ?
It must be discretized according to the first moment of each task .
And then we found out , Those of great value can be put forward . Because if a smaller one is put , It must be bigger and better .
Then we can do it step by step .
c o d e code code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n;
struct node
{
long long v, s, t;
}a[5010];
long long S[5010], b[10010];
long long f[5010];
bool cmp(node x, node y)
{
return x.s<y.s;
}
bool cmp2(node x, node y)
{
return x.v>y.v;
}
void get_point()
{
for(long long i=1; i<=n; i++)
S[i]=max(S[i-1]+1, a[i].s);
}
void lsh()
{
for(long long i=1; i<=n; i++)
{
int j=1;
while(S[j]<a[i].s) j++;
a[i].s=j;
}
}
bool find_(long long x, long long i)
{
if(S[x]>a[i].t)
return 0;
if(f[x]==0)
{
f[x]=i;
return 1;
}
long long j=f[x];
if(a[i].t>a[j].t)
return find_(x+1, i);
else if(find_(x+1, j))
{
f[x]=i;
return 1;
}
return 0;
}
int main()
{
scanf("%lld", &n);
for(long long i=1; i<=n; i++)
scanf("%lld%lld%lld", &a[i].s, &a[i].t, &a[i].v);
sort(a+1, a+1+n, cmp);
get_point();
sort(a+1, a+1+n, cmp2);
lsh();
long long ans=0;
for(long long i=1; i<=n; i++)
if(find_(a[i].s, i))
ans+=a[i].v;
printf("%lld", ans);
return 0;
}
边栏推荐
- Selenium使用之解决‘chromedriver‘ executable needs to be in PATH.报错信息
- clickhouse 20.x 分布式表测试与chproxy的部署(二)
- PCIE知识点-011:PCIE 配置能力结构与协议版本的关系
- Several common methods of database table query in SAP ABAP system
- IDEA的修改背景照片and使用技巧
- Selenium uses' chromedriver 'executable needs to be in path Error reporting information
- Qt(四)使用代码与UI文件混合开发
- Golang优秀开源项目汇总
- How to add a tracked remote branch when using a single branch clone repository?
- base64和blob对图片的压缩
猜你喜欢

【集训DAY3】Delete【模拟】

Develop command line tools

浩辰CAD建筑版 2022软件安装包下载及安装教程

Qt(十三)QChart绘制折线图

档案的逻辑 | 档案收集工作

When the wechat applet activates the account, it will prompt "this account has been activated, please log in directly with the account password"

(codeforce1699)A&B (构造)

Opencv tutorial 01: introduction and installation, basic operations of pictures and videos

(2021牛客多校五)K-King of Range(单调队列/ST表)

【集训DAY3】 Section【贪心】【二分】
随机推荐
当使用single-branch clone仓库后,如何添加跟踪的远程分支?
直播软件开发,工具类的自定义弹窗效果
How to add PTZ control to the easycvr video retrieval page?
MySQL about the installation process of zip installation package
档案的逻辑 | 全宗区分和示例
如何从HoloLens中拍摄出满意的照片/视频
Allure测试报告怎么设置
【集训DAY1】Maximum benefit【离散化】【贪心】
【集训DAY2】Torch bearer【暴力】【DFS】
但斌投资峰会:论资产管理的重要性!
STL值string学习
【集训DAY1】Spy dispatch【最小生成树】
启牛2980元开户安全吗,开户这么贵吗?
图片待传递
About March 2022, apt-c-41 disguised as winrar Exe attack terminal side emergency response troubleshooting point
DNS attack protection principle
Modifying background photos and using skills of idea
Common differences between MySQL and Oracle (2)
What is the execution method of polardb for PostgreSQL's HTAP cross machine parallel query?
Logic of archives | holonomic distinction and examples