[BZOJ1642] [Usaco 2007 Nov] 밀킹 타임 젖 짜는 시간.

전송문

http://www.lydsy.com/JudgeOnline/problem.php?id=1642

제목의 대의.

m 개 젖 짜는 시간대 및 생산량을 정하고, 매번 짜고 나면 r분 휴식을 취하고, n분 내 최대 생산량

문제풀이

dp[i]는 이전 i개 퀘스트 최대 생산량 dp[i]=w[i]에 초치 dp[i]=max(dp[i], dp[j]+w[i]) {제j개 퀘스트 종료 시간 +r<=제i개 퀘스트 시작 시간} 이 이동을 위해 우리는 시작 시간에 따라 순서를 정해야 한다.

var
 x:array[0..1000,1..3]of longint;
 dp:array[0..1000]of longint;
 i,j,k:longint;
 n,m,r,ans:longint;
procedure sort(l,r:longint);
var i,j,k,a,b:longint;
begin
 i:=l; j:=r; a:=x[(l+r) div 2,1];
 repeat
  while x[i,1]<a do inc(i);
  while a<x[j,1] do dec(j);
  if not(i>j) then
   begin
    for k:=1 to 3 do
     begin b:=x[i,k]; x[i,k]:=x[j,k]; x[j,k]:=b; end;
    inc(i); dec(j);
   end;
 until i>j;
 if l<j then sort(l,j);
 if i<r then sort(i,r);
end;

function max(a,b:longint):longint;
begin
 if a>b then exit(a) else exit(b);
end;

begin
 readln(n,m,r);
 for i:=1 to m do
  readln(x[i,1],x[i,2],x[i,3]);
 sort(1,m); {x[i,1]}
 ans:=0;
 for i:=1 to m do
  begin
   dp[i]:=x[i,3];
   for j:=1 to i-1 do
    if x[j,2]+r<=x[i,1]
    then dp[i]:=max(dp[i],dp[j]+x[i,3]);
   ans:=max(ans,dp[i]);
  end;
 writeln(ans);
end.