Milking Time---poj3616(简单dp)
2024-09-26 02:04:58
题目链接:http://poj.org/problem?id=3616
题意:人从奶牛身上挤奶有m个时间段(1----n),每个时间段包含 s e f 表示从 s 到 e 的这段时间可以获得 f 单位的牛奶,每次一个时间段结束后休息 r 小时进入下一时间段
我们可以把休息的r小时加到每个时间段的结束时间上,这样就可以直接进入下一时间断了,我们按开始时间排序。。
然后就类似于最长上升子序列了
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 1100
struct node
{
int s, e, f;
}a[N];
int cmp(node p, node q)
{
if(p.s!=q.s)
return p.s<q.s;
return p.e<q.e;
}
int dp[N];
int main()
{
int n, m, r;
while(scanf("%d %d %d", &n, &m, &r)!=EOF)
{
memset(a, , sizeof(a));
memset(dp, , sizeof(dp));
for(int i=; i<m; i++)
{
scanf("%d%d%d", &a[i].s, &a[i].e, &a[i].f);
a[i].e+=r;
}
sort(a, a+m, cmp);
int ans=;
for(int i=; i<m; i++)
{
dp[i] = a[i].f;
for(int j=; j<i; j++)
{
if(a[j].e<=a[i].s)
{
dp[i]=max(dp[i], dp[j]+a[i].f);
}
}
ans=max(ans, dp[i]);
}
printf("%d\n", ans);
}
return ;
}
最新文章
- ASP.NET Core 中文文档 第三章 原理(7)配置
- Oracle Database 12c Release 1下载安装(自身经历)
- [POI2008]KLO &;&; POC
- 浩瀚技术 安卓版移动开单手持微POS PDA无线移动开单软件 -安卓版移动手持开单设备
- 第十六章 综合实例——《跟我学Shiro》
- Angularjs,WebAPI 搭建一个简易权限管理系统 —— 基本功能演示(二)
- Java集合---HashSet的源码分析
- 排序算法总结(一)插入排序【Insertion Sort】
- JAVA类与对象(四)----成员变量与局部变量 、成员方法、构造方法
- win7/8下VirtualBox虚拟共享文件夹设置
- 关于java的continue、break关键字用法
- boost::bind的使用方法
- js设计模式--迭代器模式
- 1.3浅谈Spring(IOC容器的实现)
- MySQL和Oracle的区别
- solrcloud编辑zookeeper上的配置文件的方法
- XML解析技术-dom4j
- some working learning总结学习(二)
- sql1032n sql6048n db2start启动不了 db2修改hostname
- jquery is()和has()方法