3616 Milking Time

問題（外部リンク）

3616 -- Milking Time

実装の概要

「ある時点までに採れるミルクの量」を保存しつつ動的計画法で解きます。事前にインターバルを搾乳開始時を基準にソートし、その時間になったら直前までのミルクの量と新たに採れるミルクの量を足して「未来の」データとして保存します。
未来の時点の決め方ですが、ぎりぎりn-1で搾乳が終わった場合の処理を単純化するために「休憩が終わった時点でミルク取得」と考えた方がシンプルになるかと思います。そのためには配列も余分に準備しておく必要があるので注意。

public class Main {

	public static void main(String[] args) throws IOException {
		//ここから入力受付＆初期化
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmpArray = br.readLine().split(" ");

		int n = Integer.parseInt(tmpArray[0]);
		int m = Integer.parseInt(tmpArray[1]);
		int r = Integer.parseInt(tmpArray[2]);

		Interval[] intervals = new Interval[m];

		for(int i = 0; i < m; i++){
			tmpArray = br.readLine().split(" ");

			intervals[i] = new Interval(Integer.parseInt(tmpArray[0]),
					Integer.parseInt(tmpArray[1]), Integer.parseInt(tmpArray[2]), r);
		}
		//初期化終了

		//startについてソート
		Arrays.sort(intervals);
		int milk[] = new int[n+r+1];

		int intervalIndex = 0;
		for(int i = 0; i < milk.length ; i++){
			//基本的には前の値を引き継ぐが、
			//既に上書き済みの値があればより大きい方を採用
			if(i != 0) {
				milk[i] = Math.max(milk[i - 1], milk[i]);
			}

			Interval tmpIntval;
			//startが同タイミングのものも含めここで処理
			while(intervalIndex < m && (tmpIntval = intervals[intervalIndex]).start == i){
				int tmpMilk = tmpIntval.efficiency + milk[i];
				//休憩終了時点で搾乳完了という扱い
				milk[tmpIntval.end + tmpIntval.rest] = Math.max(tmpMilk, milk[tmpIntval.end + tmpIntval.rest]);
				intervalIndex++;
				if(intervalIndex == m){
					break;
				}
				tmpIntval = intervals[intervalIndex];
			}
		}
		System.out.println(milk[milk.length - 1]);
	}
}

class Interval implements Comparable<Interval>{
	int start;
	int end;
	int efficiency;
	int rest; //注　多分いらない

	public Interval(int start, int end, int efficiency, int rest){
		this.start = start;
		this.end = end;
		this.efficiency = efficiency;
		this.rest = rest;
	}

	public int compareTo(Interval intvl){
		return this.start - intvl.start;
	}
}