poj 3616 Milking Time -DP（带权重的区间动态规划）

poj 3616 Milking Time ---DP（带权重的区间动态规划）

题目：http://poj.org/problem?id=3616

这题就是一个小小变形的带权重的任务调度问题 --interval scheduling--

思路：首先按照每个区间的结束时间排序，再进行预处理：算出与每个区间相互兼容的最大区间下标保存在P数组里。

状态：dp[i]=max{ dp[i-1],dp[p[i]]+w[i] } 

代码：1A

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAX_M=1001;
int dp[MAX_M],p[MAX_M];
struct job{
	int s,t,w;
};
job njob[MAX_M];
bool Cmp(job a,job b){
	return a.t<b.t;
}
bool Iscompatible(job a,job b,int R){
	if(b.s>=a.t+R || b.t+R<=a.s)return 1;
	else return 0;
}
void Calculate_P(int M,int R){
	p[1]=0;
	for(int i=M;i>1;i--){
		int k=i-1;
		while(k>0 && !Iscompatible(njob[i],njob[k],R))
			k--;
		p[i]=k;	
	}
}
int main()
{
	int N,M,R;
	while(cin>>N>>M>>R){
		for(int i=1;i<=M;i++){
			cin>>njob[i].s>>njob[i].t>>njob[i].w; 
		} 
		sort(njob+1,njob+1+M,Cmp);
		Calculate_P(M,R);
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=M;i++){
			dp[i]=max(dp[i-1],dp[p[i]]+njob[i].w);
		}
		cout<<dp[M]<<endl;
	}
}