当前位置:网站首页>POJ - 3616 Milking Time(DP+LIS)
POJ - 3616 Milking Time(DP+LIS)
2022-07-07 08:31:00 【WA_ automata】
POJ - 3616 Milking Time
Description
Bessie is such a hard-working cow. In fact, she is so focused on maximizing her productivity that she decides to schedule her next N (1 ≤ N ≤ 1,000,000) hours (conveniently labeled 0…N-1) so that she produces as much milk as possible.
Farmer John has a list of M (1 ≤ M ≤ 1,000) possibly overlapping intervals in which he is available for milking. Each interval i has a starting hour (0 ≤ starting_houri ≤ N), an ending hour (starting_houri < ending_houri ≤ N), and a corresponding efficiency (1 ≤ efficiencyi ≤ 1,000,000) which indicates how many gallons of milk that he can get out of Bessie in that interval. Farmer John starts and stops milking at the beginning of the starting hour and ending hour, respectively. When being milked, Bessie must be milked through an entire interval.
Even Bessie has her limitations, though. After being milked during any interval, she must rest R (1 ≤ R ≤ N) hours before she can start milking again. Given Farmer Johns list of intervals, determine the maximum amount of milk that Bessie can produce in the N hours.
Input
- Line 1: Three space-separated integers: N, M, and R
- Lines 2…M+1: Line i+1 describes FJ’s ith milking interval withthree space-separated integers: starting_houri , ending_houri , and efficiencyi
Output
- Line 1: The maximum number of gallons of milk that Bessie can product in the N hours
Sample Input
12 4 2
1 2 8
10 12 19
3 6 24
7 10 31
Sample Output
43
The cow is in n Milk production in time , Farmers have m You can milk for a while , Every period of time has a starting point strat, The end point end, And the milking volume during this period w. After each milking , Cows must rest r Time . Ask how much milk you can get under the most reasonable milking arrangement ?
First, sort the interval according to the end time , Then according to the i Whether to choose or not to carry out dynamic planning
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
struct Node
{
int l,r,val;
}a[N];
int dp[N];
bool cmp(Node A,Node B)
{
return A.r<B.r;
}
int main()
{
int n,m,r;cin>>n>>m>>r;
for(int i=1;i<=m;i++)
{
cin>>a[i].l>>a[i].r>>a[i].val;
a[i].r+=r;
}
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++)
{
dp[i]=a[i].val;
for(int j=1;j<i;j++)
if(a[j].r<=a[i].l)
dp[i]=max(dp[i],dp[j]+a[i].val);
}
int ans=0;
for(int i=1;i<=m;i++)
ans=max(ans,dp[i]);
cout<<ans<<endl;
return 0;
}
边栏推荐
- 在Rainbond中实现数据库结构自动化升级
- Deit learning notes
- SSM 整合
- [go ~ 0 to 1] obtain timestamp, time comparison, time format conversion, sleep and timer on the seventh day
- Function extension, attribute extension and non empty type extension in kotlin
- 2 - 3 arbre de recherche
- Interpreting the practical application of maker thinking and mathematics curriculum
- [paper reading] icml2020: can autonomous vehicles identify, recover from, and adapt to distribution shifts?
- [hard core science popularization] working principle of dynamic loop monitoring system
- 【雅思口语】安娜口语学习记录 Part3
猜你喜欢
Input of mathematical formula of obsidan
Rainbow version 5.6 was released, adding a variety of installation methods and optimizing the topology operation experience
Opencv learning note 5 - gradient calculation / edge detection
Exercise arrangement 2.10, 11
BiSeNet的特点
Openvscode cloud ide joins rainbow integrated development system
eBPF Cilium实战(1) - 基于团队的网络隔离
Opencv learning note 3 - image smoothing / denoising
2-3查找樹
OpenVSCode云端IDE加入Rainbond一体化开发体系
随机推荐
Opencv learning note 3 - image smoothing / denoising
Ebpf cilium practice (2) - underlying network observability
[untitled]
DeiT学习笔记
National standard gb28181 protocol video platform easygbs adds streaming timeout configuration
Iptables' state module (FTP service exercise)
Function extension, attribute extension and non empty type extension in kotlin
在Rainbond中实现数据库结构自动化升级
Improve the delivery efficiency of enterprise products (1) -- one click installation and upgrade of enterprise applications
[go ~ 0 to 1] obtain timestamp, time comparison, time format conversion, sleep and timer on the seventh day
Low success rate of unit test report
Learn how to compile basic components of rainbow from the source code
MES系统,是企业生产的必要选择
提高企业产品交付效率系列(1)—— 企业应用一键安装和升级
MySQL introduction - crud Foundation (establishment of the prototype of the idea of adding, deleting, changing and searching)
It's too true. There's a reason why I haven't been rich
Splunk子查询模糊匹配csv中字段值为*
解读创客思维与数学课程的实际运用
Through the "last mile" of legal services for the masses, fangzheng Puhua labor and personnel law self-service consulting service platform has been frequently "praised"
字符串操作