BZOJ 1642: [Usaco2007 Nov]Milking Time 挤奶时间 (dp,类似LIS)
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 667 Solved: 389 [Submit][Status][Discuss]
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 个小时内，最大的挤奶的量。
Input
第1行三个整数N，M，R.接下来M行，每行三个整数Si，Ei，Pi．
Output
最大产奶量．
Sample Input
12 4 2 1 2 8 10 12 19 3 6 24 7 10 31
Sample Output
43
HINT
注意：结束时间不挤奶
思路：这题很像LIS啊。。由于每次结束要休息R的时间，所以把结束时间+R就好。
然后按照开始时间排序。
dp[i]表示前i个任务安排最大的挤奶量。
初始化dp[i] = a[i].val
转移的时候 dp[i] = max(dp[i],dp[j]+a[i].val) (j<i&&a[j].r<=a[i].l)
1/* ***********************************************
2Author :111qqz
3Created Time :2016年04月10日 星期日 01时50分11秒
4File Name :code/bzoj/1642.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E3+7;
34struct node
35{
36 int l,r;
37 int val;
38
39 bool operator < (node b)const
40 {
41 if (l==b.l) return r<b.r;
42 return l<b.l;
43 }
44}a[N];
45int n,m,R;
46int sum;
47int dp[N];
48
49int main()
50{
51 #ifndef ONLINE_JUDGE
52 freopen("code/in.txt","r",stdin);
53 #endif
54
55 scanf("%d %d %d",&n,&m,&R); //有点LIS的感觉...
56 for ( int i = 1 ; i <= m ; i++)
57 {
58 scanf("%d %d %d",&a[i].l,&a[i].r,&a[i].val);
59 a[i].r += R;
60 a[i].r = min(a[i].r,n);
61 }
62 sort(a+1,a+m+1);
63
64 ms(dp,0);
65 for ( int i = 1 ;i <= m ; i++) dp[i] = a[i].val;
66
67// for ( int i = 1 ; i <= m ; i++) cout<<dp[i]<<" ";
68// cout<<endl;
69 int ans = -1;
70 for ( int i = 2 ; i <= m ; i++)
71 {
72 for ( int j = 1 ; j < i ; j++)
73 {
74 if (a[j].r<=a[i].l)
75 {
76 dp[i] = max(dp[i],dp[j]+a[i].val);
77 }
78 }
79// for ( int j = 1 ; j <= m ; j++) cout<<dp[j]<<" ";
80// cout<<endl;
81 ans = max(ans,dp[i]);
82 }
83
84 printf("%d\n",ans);
85
86
87 #ifndef ONLINE_JUDGE
88 fclose(stdin);
89 #endif
90 return 0;
91}