【题意】
有头牛产奶n小时(n<=1000000),但必须在m个时间段内取奶,给定每个时间段的起始时间和结束时间以及取奶质量
且两次取奶之间须间隔r-1个小时,求最大取奶质量
【输入】
第一行n,m,r
接下来m行每行三个数字表示时间段的起始时间和结束时间以及取奶质量
【输出】
输出一个数字,表示最大取奶质量
dp
唯一需要注意的就是题目描述有问题,不是两次取奶需要间隔r小时而是r-1小时
比如说7分钟挤奶完毕,r=2,那么9分钟便可以开始挤奶
program poj3616; var n,m,r,i,j,k,s,e,p:longint; f,root:array [0..1000001] of longint; next,point,cost:array [0..1001] of longint; function quick (now:longint):longint; begin if now<=0 then exit(0) else exit(f[now]); end; begin read(n,m,r); for i:=1 to m do begin read(s,e,p); inc(s); inc(e); point[i]:=s; cost[i]:=p; next[i]:=root[e]; root[e]:=i; end; inc(n); for i:=1 to n do begin f[i]:=f[i-1]; k:=root[i]; while k<>0 do begin if quick(point[k]-r)+cost[k]>f[i] then f[i]:=quick(point[k]-r)+cost[k]; k:=next[k]; end; end; writeln(f[n]); end.