动态规划

由于奶牛每次挤奶后都要休息R小时，我们不妨把这R小时加到每个时间段的后面。每个时间段看成一个带权区间，我们要求的是不重叠区间的权值和的最大值。

O(N^2)的算法

首先对每个区间按照左端的位置升幂排序，然后进行动态规划。

状态设定

* F[i]为前i个区间，右端最大的区间为i时，所得到的最大值 

状态转移方程

* F[i]=Max{ F[k] } + W[i] (k=1..i-1 并且 right[k] <= left[i])
      o W[i]为区间i的价值
      o right[k]为区间k的右端
      o left[i]为区间i的左端 

边界条件

* F[0]=0 

目标结果

* Ans=Max{ F[i] } (i=1..M) 

#include <iostream>
#define MAX 1001
using namespace std;

typedef struct
{
	int left,right,value;
}extent;

int T,N,R,Ans;
int F[MAX];
extent E[MAX];

inline int cmp(const void *a,const void *b)
{
	return ((extent *)a)->left - ((extent *)b)->left;
}

void init()
{
	int i;
	freopen("milkprod.in","r",stdin);
	freopen("milkprod.out","w",stdout);
	cin >> T >> N >> R;
	T+=R;
	for (i=1;i<=N;i++)
	{
		scanf("%d%d%d",&E[i].left,&E[i].right,&E[i].value);
		E[i].right+=R;
	}
	qsort(E+1,N,sizeof(E[0]),cmp);
}

void dynamic()
{
	int i,j,max;
	for (i=1;i<=N;i++)
	{
		max=0;
		for (j=1;j<=i-1;j++)
			if (E[j].right<=E[i].left && F[j]>max)
				max=F[j];
		F[i]=max+E[i].value;
		if (F[i]>Ans)
			Ans=F[i];
	}
}

int main()
{
	init();
	dynamic();
	cout << Ans << endl;
	return 0;
}

<a href="http://www.ruvtex.cn/wiki/USACOMonthly/2007_11_S/Milking_Time/Chinese">挤奶时间</a>

译 By BYVoid

描述

贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的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 个小时内，最大的挤奶的量。

输入

    * 第 1 行: 三个整数 N, M, R
    * 第 2..M+1 行: 第 i+1 行 每行三个整数，为 

输出

    * 第 1 行:一个整数 在 N 个小时内，最大的挤奶的量Farmer John放入挤奶计划，开始时间，结束时间，产量。 

样例输入

12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

样例输出

43

上次修改时间 2017-02-03