当前位置:网站首页>POJ - 3616 Milking Time(DP+LIS)
POJ - 3616 Milking Time(DP+LIS)
2022-07-07 05:27:00 【WA_自动机】
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
牛在n时间内产奶,农夫有m段时间可以挤奶,每一段时间有开始点strat,结束点end,和这段时间的挤奶量w。 每一次挤奶后,牛都必须休息r时间。问在最合理的挤奶安排下挤到的最大牛奶量是多少?
首先按照结束时间排序区间,然后按照第i个区间选择与否进行动态规划
#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;
}
边栏推荐
- DeiT学习笔记
- eBPF Cilium实战(1) - 基于团队的网络隔离
- Openjudge noi 2.1 1752: chicken and rabbit in the same cage
- opencv学习笔记二——图像基本操作
- Analysis of maker education in innovative education system
- 数据中台落地实施之法
- JS copy picture to clipboard read clipboard
- [IELTS speaking] Anna's oral learning records part2
- Make LIVELINK's initial pose consistent with that of the mobile capture actor
- Low success rate of unit test report
猜你喜欢
Leetcode simple question: find the K beauty value of a number
opencv学习笔记三——图像平滑/去噪处理
JS copy picture to clipboard read clipboard
Analysis of maker education in innovative education system
使用 Nocalhost 开发 Rainbond 上的微服务应用
使用SwinUnet训练自己的数据集
2 - 3 arbre de recherche
提高企业产品交付效率系列(1)—— 企业应用一键安装和升级
Deit learning notes
SSM 整合
随机推荐
解析创新教育体系中的创客教育
Obsidan之数学公式的输入
BiSeNet的特点
Infix keyword infix expression and the use of generic extension function in kotlin
Lua 编程学习笔记
Openjudge noi 2.1 1752: chicken and rabbit in the same cage
Wang Zijian: is the NFT of Tencent magic core worth buying?
What is the function of paralleling a capacitor on the feedback resistance of the operational amplifier circuit
DeiT学习笔记
Rainbow version 5.6 was released, adding a variety of installation methods and optimizing the topology operation experience
Caractéristiques de bisenet
MES系统,是企业生产的必要选择
漏洞複現-Fastjson 反序列化
Rainbond 5.6 版本发布,增加多种安装方式,优化拓扑图操作体验
Famine cloud service management script
Splunk子查询模糊匹配csv中字段值为*
如何理解分布式架构和微服务架构呢
云原生存储解决方案Rook-Ceph与Rainbond结合的实践
使用SwinUnet训练自己的数据集
Bayes' law