退社(14501)

1.質問

質問リンク
問題の説明
コンサルタントの白俊さんが会社を辞めます.
今日からN+1日で辞めるために、残りのN日にできるだけ多くの相談をします.
白俊は秘書にできるだけ多くの相談を依頼し、秘書は1日に1回異なる人に相談を手配した.
各コンサルティングは,コンサルティングを完了するのに要する時間内にTIとコンサルティングを行う際に得られる金額Piからなる.
N=7の場合は、以下のコンサルティングスケジュールを参照してください.

1日のカウンセリングは全部で3日かかりますが、カウンセリング時にもらえる金額は10です.5日間のお問い合わせは2日間かかりますが、受け付けられる金額は15です.
相談にかかる時間は1日以上かかる場合がありますので、すべての相談はできません.例えば、1日に問い合わせを行った場合、2日、3日に問い合わせをすることはできません.2日に問い合わせをすれば、3、4、5、6日には問い合わせができない.
なお、N+1日は会社にいないため、6,7日は相談できません.
退職前にカウンセリングを行う最大の利益は1日、4日、5日にカウンセリングを行うことであり、その際の利益は10+20+15=45である.
商談がうまくいけば、白俊に最大の収益をもたらす計画を立ててください.
入力
第1行はN(1≦N≦15)を与える.
2行目からN行目まで、TIとPiはスペースで区切られ、1日からN日まで順次与えられる.(1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
しゅつりょく
1行目は白俊が得られる最大の利益を出力する.

2.解答

2-1. 条件

N+1日で退社.

の問い合わせを行うのにかかる時間は1日より大きい場合がありますので、すべての問い合わせはできません.

2-2. に答える

DFSの問題をたくさん解いた人は感じます
i翌日に相談するかしないかに分けて、完全探索を実施すれば解決できる問題.
ここに整理して和音を編みましょうか?

        /**
	 * @param {integer} day 일자
	 * @param {integer} profit 이익
	 * @return {integer} day일 째부터 고려해서 퇴사일에 얻을 수 있는 최대 이익
	 */
	static int max(int day, int profit) {
		// 퇴사일을 넘어갈 땐 잘못된 탐색이므로 아주 작은 값을 리턴
		if (day > n + 1) return -987654321;
			
		// 퇴사일일 땐 그동안 모아온 이익을 리턴
		if (day == n + 1) return profit;
			
		// day일에 일을 안하고 다음 날로 넘어가는 경우 vs day일에 일을 하고 t[day]후로 넘어가는 경우 
		return Math.max(max(day + 1, profit), max(day + t[day], profit + p[day]));
	}

もちろん、このようにしても正解が得られますが、繰り返しの計算が非常に多いことがわかります.
再帰呼び出しによる完全なナビゲーションの場合、合計は2^Nです.
彼らは、重複した日付に対して得られる最大の利益を繰り返し呼び出しているからです.
パフォーマンスの調整が必要な場合があります.
では、利益をパラメータとしない場合、最大値関数の回復性を実現するのはどうでしょうか.
計算結果をmemoという名前の配列に保存し、繰り返し計算を防止します.
では、コメントをmax関数に適用し、コードを再記述します.
dayパラメータのみを受け入れ、dayからN+1日で退職したときに得られる最大の利益を返します.
今回作成した関数は純粋な関数で、同じパラメータ(日)を入力すると同じ値(maxProfit)が返されるので、コメント修復を適用できます.
(もちろん、外部のmemo、t、p配列に依存するが、t、p配列は不変であり、memoは繰返し計算を避けるためであるため、純粋な関数であっても構わない.)

       /**
	 * @param {integer} day 일자
	 * @return {integer} day일 째부터 고려해서 퇴사일에 얻을 수 있는 최대 이익
	 */
	static int max(int day) {
		// 퇴사일을 넘어갈 땐 잘못된 탐색이므로 아주 작은 값을 리턴
		if (day > n + 1) return -987654321;
		
		// 퇴사일일 땐 0을 리턴
		if (day == n + 1) return 0;
		
		// 이미 계산을 했었다면 계산값 바로 리턴 
		if (memo[day] != -1) return memo[day];
		
		/**
		 * day일 째부터 고려해서 퇴사일에 얻을 수 있는 최대 이익 = max(
		 * 		(day + 1)일 째부터 고려해서 퇴사일에 얻을 수 있는 최대 이익,
		 * 	    (day + t[day])일 째부터 고려해서 퇴사일에 얻을 수 있는 최대 이익 + day일에 일하면 받는 공수
		 * )
		 */
		return memo[day] = Math.max(max(day + 1), max(day + t[day]) + p[day]);
	}

これは、注釈配列を埋め込むだけなので、合計時間の複雑さをNにします.
上で完全に検索したところ、2^Nに比べてかなりの調整でした.

3.完全なコード

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int n, t[], p[], memo[];
	
	/**
	 * @param {integer} day 일자
	 * @return {integer} day일 째부터 고려해서 퇴사일에 얻을 수 있는 최대 이익
	 */
	static int max(int day) {
		// 퇴사일을 넘어갈 땐 잘못된 탐색이므로 아주 작은 값을 리턴
		if (day > n + 1) return -987654321;
		
		// 퇴사일일 땐 0을 리턴
		if (day == n + 1) return 0;
		
		// 이미 계산을 했었다면 계산값 바로 리턴 
		if (memo[day] != -1) return memo[day];
		
		/**
		 * day일 째부터 고려해서 퇴사일에 얻을 수 있는 최대 이익 = max(
		 * 		(day + 1)일 째부터 고려해서 퇴사일에 얻을 수 있는 최대 이익,
		 * 	    (day + t[day])일 째부터 고려해서 퇴사일에 얻을 수 있는 최대 이익 + day일에 일하면 받는 공수
		 * )
		 */
		return memo[day] = Math.max(max(day + 1), max(day + t[day]) + p[day]);
	}
	
	/**
	 * @param {integer} day 일자
	 * @param {integer} profit 이익
	 * @return {integer} day일 째부터 고려해서 퇴사일에 얻을 수 있는 최대 이익
	 */
	static int max(int day, int profit) {
		// 퇴사일을 넘어갈 땐 잘못된 탐색이므로 아주 작은 값을 리턴
		if (day > n + 1) return -987654321;
			
		// 퇴사일일 땐 그동안 모아온 이익을 리턴
		if (day == n + 1) return profit;
			
		// day일에 일을 안하고 다음 날로 넘어가는 경우 vs day일에 일을 하고 t[day]후로 넘어가는 경우 
		return Math.max(max(day + 1, profit), max(day + t[day], profit + p[day]));
	}
	
	public static void main(String[] args) throws Exception {
		n = Integer.parseInt(br.readLine());
		t = new int[n + 1];
		p = new int[n + 1];
		memo = new int[n + 1];
		
		for (int i = 1; i <=n; i++) {
			String[] s = br.readLine().split(" ");
			
			t[i] = Integer.parseInt(s[0]);
			p[i] = Integer.parseInt(s[1]);
			memo[i] = -1;
		}
		
		bw.write(max(1) + "");
		bw.close();
	}
}