题目链接: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 ;
}

最新文章

  1. ASP.NET Core 中文文档 第三章 原理(7)配置
  2. Oracle Database 12c Release 1下载安装(自身经历)
  3. [POI2008]KLO &amp;&amp; POC
  4. 浩瀚技术 安卓版移动开单手持微POS PDA无线移动开单软件 -安卓版移动手持开单设备
  5. 第十六章 综合实例——《跟我学Shiro》
  6. Angularjs,WebAPI 搭建一个简易权限管理系统 —— 基本功能演示(二)
  7. Java集合---HashSet的源码分析
  8. 排序算法总结(一)插入排序【Insertion Sort】
  9. JAVA类与对象(四)----成员变量与局部变量 、成员方法、构造方法
  10. win7/8下VirtualBox虚拟共享文件夹设置
  11. 关于java的continue、break关键字用法
  12. boost::bind的使用方法
  13. js设计模式--迭代器模式
  14. 1.3浅谈Spring(IOC容器的实现)
  15. MySQL和Oracle的区别
  16. solrcloud编辑zookeeper上的配置文件的方法
  17. XML解析技术-dom4j
  18. some working learning总结学习(二)
  19. sql1032n sql6048n db2start启动不了 db2修改hostname
  20. jquery is()和has()方法

热门文章

  1. HDU 4969 Just a Joke(积分)
  2. tensorflow 之模型的保存与加载(三)
  3. 【转】Cocos2d-x 3.1.1 学习日志6--30分钟了解C++11新特性
  4. C#数组、ArrayList和List&lt;T&gt;
  5. db_keep_cache_size參数的控制范围測试
  6. python文章的抓取
  7. mysql 分数表实现排名
  8. 请谈谈对SOA的认识。
  9. XStream的基本使用
  10. JDB调试之小试牛刀