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;}}