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