poj 3616 Milking Time dp

缘起

日常浪费生命 poj 3616 Milking Time

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
[0,..,N-1]给你M个区间（可能重叠），然后每个区间有产出，但是一旦奶牛在此区间产奶的话,产完需要休息R
分钟. 问如何安排产奶时间使得产奶量最大.

【输入】
N,M,R 
1 ≤ N ≤ 1,000,000
1 ≤ M ≤ 1,000
1 ≤ R ≤ N
然后M行，每行三个数字 s,e,y 表示奶牛在[s,e]区间产奶产量是y
0<=s<e<=N
1 ≤ yi ≤ 1,000,000

【输出】
最大产奶量

【样例输入】
12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

【样例输出】
43

【限制】
1s

首先将每个区间往后延续R的距离. 然后按照区间的结束时间点升序排序. 令dp[i]为以第i个区间结束的最大产奶量. 则如何决定dp[i]呢? 其实和原先经典连续片段和（【1】）是一个路子.

dp[i]=max{dp[1,…,x]+第i个区间的产奶量}

其中x是最大的那个终点<=第i个区间的起点. 虽然M只有1000, 我们完全可以忍受O(n^2)的算法，但是其实这里还是可以使用二分查找优化的. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,m,r,dp[1005];
struct cc
{
	int s,e,y;
	bool operator < (cc c)
	{
		return e<c.e;
	}
}zz[1005];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d%d", &n, &m,&r);
	for (int i = 0; i<m;i++)
	{
		scanf("%d%d%d", &zz[i].s, &zz[i].e, &zz[i].y);
		zz[i].e+=r;
	}
	sort(zz,zz+m);
	dp[0] = zz[0].y;
	for (int i = 1; i<m;i++)
	{
		dp[i] = zz[i].y;
		for (int j = 0; j<i; j++)
		{
			if (zz[j].e<=zz[i].s)
			{
				dp[i] = max(dp[i],dp[j]+zz[i].y);
			}
			else break;
		}
	} // O(n^2)真香!
	for (int i = 0; i<m-1; i++) // 最后还要求最大
	{
		if (dp[m-1]<dp[i])
		{
			dp[m-1] = dp[i];
		}
	}
	printf("%d\n", dp[m-1]);
	return 0;
}

ac情况

Status Accepted
Memory 100kB
Length 791
Lang C++
Submitted 2019-08-26 12:31:17
Shared
RemoteRunId 20801825

参考

【1】https://yfsyfs.github.io/2019/07/20/%E7%BB%8F%E5%85%B8dpdp-%E6%B1%82%E6%9C%80%E5%A4%A7%E7%89%87%E6%AE%B5%E5%92%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97/