【POJ】3616 Milking Time(dp)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 10898 | Accepted: 4591 |
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
Source
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[];
struct c{
int begin,end,e;
}a[];
bool cmp(c a,c b)
{
if(a.begin<b.begin) return true;
if(a.begin==b.begin&&a.end<b.end) return true;
return false;
}
int main()
{
int n,m,r;
scanf("%d%d%d",&n,&m,&r);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&a[i].begin,&a[i].end,&a[i].e);
a[i].end+=r;// 实际的结束时间还需要加上休息时间
}
sort(a+,a++m,cmp);
for(int i=;i<=m;i++)
{
dp[i]=a[i].e;
for(int j=;j<=i;j++)
{
if(a[j].end<=a[i].begin)
dp[i]=max(dp[i],dp[j]+a[i].e);
}
}
printf("%d",*max_element(dp,dp++m));
return ;
}
最新文章
- UIView
- ASP.NET4.5Web API及非同步程序开发系列(2)
- inner join on, left join on, right join on的区别与介绍
- MVC模式(Model View Controller)下实现数据库的连接,对数据的删,查操作
- 巧用Systemtap注入延迟模拟IO设备抖动
- How to fix “The program can’t start because MSVCR110.dll is missing from your computer.” error on Windows
- 使用WMI控制Windows进程 和服务
- 如何实现数字lcd显示效果(原创)
- [LeetCode]题解(python):131-Palindrome Partitioning
- ajax原理图解
- deviceOne -- js的本地搜索
- 一起来学Go --- (go的简介以及环境的安装)
- return 的返回值与结束功能
- Django web框架开发基础-django实现留言板功能
- node.js获取参数的常用方法
- BZOJ 3123 【SDOI2013】 森林
- bzoj 1012 BST 支持插入,区间最大
- Uncaught Error: artDialog: Document types require more than xhtml1.0
- sql server获取后天距离某一日期还有多少周的写法
- 获取iOS应用中当前处于Activity状态的ViewController
热门文章
- Python面向对象 --- 新旧式类、私有方法、类属性和类方法、静态方法
- Apache .htaccess文件
- Spring AOP的使用报错!
- caffe中的Local Response Normalization (LRN)有什么用,和激活函数区别
- 【剑指offer】二叉搜索树转双向链表,C++实现
- HDU3047 Zjnu Stadium 【带权并查集】
- BZOJ2243 SDOI2011 染色 【树链剖分】
- 【Codeforces】Round #488 (Div. 2) 总结
- koa2 中间件里面的next到底是什么
- You&#39;re Given a String...