[BZOJ1642]&&[Usaco2007 Nov]Milking Time 挤奶时间

2014-06-23
竞赛题解 / 动态规划
BZOJUSACO

描述 Description

贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的 N (1 ≤ N ≤ 1,000,000) 个小时，标记为 0..N-1。 Farmer John 计划好了 M (1 ≤ M ≤ 1,000) 个可以挤奶的时间段。每个时间段有一个开始时间 (0 ≤ 开始时间 ≤ N), 和一个结束时间 (开始时间 < 结束时间 ≤ N), 和一个产量 (1 ≤ 产量 ≤ 1,000,000) 表示可以从贝茜挤奶的数量。Farmer John 从分别从开始时间挤奶，到结束时间为止。每次挤奶必须使用整个时间段。 但即使是贝茜也有她的产量限制。每次挤奶以后，她必须休息 R (1 ≤ R ≤ N) 个小时才能下次挤奶。给定 Farmer John 计划的时间段，请你算出在 N 个小时内，最大的挤奶的量。

输入格式 InputFormat

第 1 行三个整数 N，M，R. 接下来 M 行，每行三个整数 Si，Ei，Pi．

输出格式 OutputFormat

最大产奶量．

样例输入 SampleInput

900 73 9
198 362 239
189 262 451
402 545 125
585 795 423
370 562 443
508 701 513
12 361 407
66 762 240
727 743 225
418 432 427
297 541 72
860 863 424
265 573 127
424 607 282
606 741 366
593 858 248
836 862 508
423 812 138
780 824 396
894 895 36
143 431 189
27 308 46
605 664 348
119 317 34
885 888 351
214 783 250
471 745 447
74 391 282
703 881 287
896 897 468
589 813 6
454 678 133
481 548 380
686 876 28
236 275 490
695 799 397
220 310 213
849 876 181
438 705 1
287 495 411
0 83 151
146 274 457
196 326 16
814 855 228
81 135 138
818 868 204
377 492 440
754 858 431
712 812 72
67 808 394
755 879 505
393 449 215
485 866 45
355 619 211
576 804 464
807 899 156
474 578 120
82 667 276
700 827 284
530 724 288
262 585 118
271 866 166
814 892 80
295 641 396
640 650 376
1 465 234
87 667 79
833 838 494
701 853 406
212 310 376
823 875 86
464 745 171
380 419 245

样例输出 SampleOutput

3831

来源 Source

Silver

BZOJ 1642

代码 Code

DP. 注意结束时间是不挤奶的，也就是结束时间那一刻开始休息。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7fffffff/27.11;
struct data
{
    int s,e,p;
    bool operator < (const data &temp) const
    {
        return s<temp.s;
    }
}a[10005];
int f[10005];
int i,j,t,n,m,l,r,k,z,y,x,ans;
inline int read()
{
    int x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main()
{
    n=read();m=read();r=read();
    for (i=1;i<=m;i++)
    {
        a[i].s=read();a[i].e=read();a[i].p=read();
    }
    sort(a+1,a+m+1);
    ans=-inf;
    for (i=1;i<=m;i++)
    {
        f[i]=a[i].p;
        for (j=1;j<i;j++) if (a[j].e+r<=a[i].s) f[i]=max(f[i],f[j]+a[i].p);
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}