P2889 [USACO07NOV]挤奶的时间Milking Time

普通的dp

休息时间R其实就是把结束时间后移R个单位而已。但是终点也需要后移R位到n+R

每个时间段按起始时间排序,蓝后跑一遍普通的线性dp即可

注意起点是0

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int max(int &a,int &b){return a>b?a:b;}
struct data{
int l,r,val;
void Init(){scanf("%d%d%d",&l,&r,&val);}
bool operator < (const data &tmp) const{
return l<tmp.l;
}
}a[];
int n,m,R,f[];
int main(){
scanf("%d%d%d",&n,&m,&R);
for(int i=;i<=m;++i) a[i].Init();
sort(a+,a+m+); int k=;
for(int i=;i<=n+R;++i){
if(i) f[i]=max(f[i],f[i-]);
for(;a[k].l==i&&k<=m;++k)
f[a[k].r+R]=max(f[a[k].r+R],f[i]+a[k].val);
}printf("%d",f[n+R]);
return ;
}

最新文章

  1. Asp.Net WebApi开发注意
  2. 修改WebBrowser控件的内核解决方案
  3. [转]Ionic最佳实践-使用模态窗口modal
  4. HDU-3874 Necklace 线段树+离线
  5. requireJS源码流程分析
  6. 来更新一篇blog吧
  7. Ftp的断点下载实现
  8. 一次处理ORA-07445的历险记(转)
  9. 深夜,用canvas画一个时钟
  10. 输出A打头的字符串
  11. 放弃FreeMark?
  12. 响应式移动端去除css的hover和jq的hover还有input在苹果下的默认样式
  13. R语言︱决策树族——随机森林算法
  14. 2393Cirno的完美算数教室 容斥
  15. Linux之使用网络
  16. substr函数学习
  17. c# 怎么读取web.config中的配置项
  18. 使用Eclipse自带的Axis1插件生成Web Service服务端客户端
  19. 腾讯大讲堂 微信红包系统设计 &amp; 优化
  20. oracle ORA-00119和ORA-00132解决方法

热门文章

  1. Mysql数据库操作复习,增删改查
  2. OpenJ_Bailian - 4152 最佳加法表达式 dp
  3. Primitive Data Types
  4. 图论——最小生成树_prim
  5. 异步IO
  6. 学习计划 mysql 整数类型后面的数字,是什么意思?
  7. swiper跳转制定页面
  8. nodejs(五)同步异步--USING SETTIMEOUT INSTEAD OF SETINTERVAL TO FORCE SERIALIZATION
  9. 蒙特卡洛模拟(Monte Carlo simulation)
  10. Approximate Inference