【bzoj1672】[USACO2005 Dec]Cleaning Shifts 清理牛棚
题目描述
Farmer John's cows, pampered since birth, have reached new heights of fastidiousness. They now require their barn to be immaculate. Farmer John, the most obliging of farmers, has no choice but hire some of the cows to clean the barn. Farmer John has N (1 <= N <= 10,000) cows who are willing to do some cleaning. Because dust falls continuously, the cows require that the farm be continuously cleaned during the workday, which runs from second number M to second number E during the day (0 <= M <= E <= 86,399). Note that the total number of seconds during which cleaning is to take place is E-M+1. During any given second M..E, at least one cow must be cleaning. Each cow has submitted a job application indicating her willingness to work during a certain interval T1..T2 (where M <= T1 <= T2 <= E) for a certain salary of S (where 0 <= S <= 500,000). Note that a cow who indicated the interval 10..20 would work for 11 seconds, not 10. Farmer John must either accept or reject each individual application; he may NOT ask a cow to work only a fraction of the time it indicated and receive a corresponding fraction of the salary. Find a schedule in which every second of the workday is covered by at least one cow and which minimizes the total salary that goes to the cows.
输入
* Line 1: Three space-separated integers: N, M, and E. * Lines 2..N+1: Line i+1 describes cow i's schedule with three space-separated integers: T1, T2, and S.
输出
* Line 1: a single integer that is either the minimum total salary to get the barn cleaned or else -1 if it is impossible to clean the barn.
样例输入
3 0 4
0 2 3
3 4 2
0 0 1
样例输出
5
提示
约翰有3头牛,牛棚在第0秒到第4秒之间需要打扫.第1头牛想要在第0,1,2秒内工作,为此她要求的报酬是3美元.其余的依此类推. 约翰雇佣前两头牛清扫牛棚,可以只花5美元就完成一整天的清扫.
题解
线段树或动态规划
一道看似很水的题。
由于USACO数据较水,而且bzoj有O2优化,于是一开始试着用dp来求解。
然后就AC了。。。AC了。。。AC了。。。
而且速度飞快啊。
看了正解才知道是线段树的题,仔细想想也不难。
这里直接搬运黄学长的blog:
http://hzwer.com/3869.html
代码是dp的,不需任何优化即可通过。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct data
{
int t1 , t2;
long long s;
}a[10001];
long long f[10001];
bool cmp(data a , data b)
{
return a.t1 < b.t1;
}
int main()
{
int n , m , e , i , j;
long long ans = 0x3f3f3f3f3f3f3f3fll;
scanf("%d%d%d" , &n , &m , &e);
for(i = 0 ; i < n ; i ++ )
{
scanf("%d%d%lld" , &a[i].t1 , &a[i].t2 , &a[i].s);
}
sort(a , a + n , cmp);
memset(f , 0x3f , sizeof(f));
for(i = 0 ; i < n ; i ++ )
if(a[i].t1 <= m)
f[i] = a[i].s;
for(i = 1 ; i < n ; i ++ )
for(j = 0 ; j < i ; j ++ )
if(a[j].t2 + 1 >= a[i].t1)
f[i] = min(f[i] , f[j] + a[i].s);
for(i = 0 ; i < n ; i ++ )
if(a[i].t2 >= e)
ans = min(ans , f[i]);
if(ans == 0x3f3f3f3f3f3f3f3fll)
printf("-1\n");
else
printf("%lld\n" , ans);
return 0;
}
最新文章
- BZOJ 3289: Mato的文件管理[莫队算法 树状数组]
- Android开发笔记之《Window下安装Ubuntu双系统,Grub无法显示Window选项》
- .net的垃圾回收机制简述
- Cisco IOS IP Service Level Agreementv (IP SLA)
- 精妙SQL语句收集
- ASPxGridView中DetailRow的使用
- MVC&;amp;&;amp;MVP
- inpuy type=date
- 用户 IIS APPPOOL\DefaultAppPool 登录失败的解决方法
- JSON解析保存在类中
- Spark Streaming揭秘 Day20 动态Batch size实现初探(上)
- SpringMVC可以配置多个拦截后缀*.html和.do等
- Flux工作流
- LR使用Java User协议环境报错Please add the <;JDK>;\bin to the path and try again
- a++与 ++a
- HL7体系入门级介绍【转】
- 追求极致的用户体验ssr(基于vue的服务端渲染)
- Hadoop 系列文章(二) Hadoop配置部署启动HDFS及本地模式运行MapReduce
- ubuntu安装odbc及(mysql驱动)
- GridView和DataFormatString 日期格式 精确小数点后位数