Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM 340 CsCourses

|  SRM 340 CsCourses - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 340 CsCourses - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7505

  • 動的計画法+辞書順最小経路復元
    • 状態は [month][theoreticalValue][practicalValue]
    • 経路復元付きの場合はメモ化再帰すると楽。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CsCourses {
	int len;
	int[] tv;
	int[] pv;
	int[] exp;
	int bound;
	
	int[][][] memo = new int[51][51][51];
	int[][][] memo_prev = new int[51][51][51];

	
	public int dfs(int month, int ntv, int npv) {
		if (ntv >= bound && npv >= bound) {
			return 0;
		}
		if (memo[month][ntv][npv] >= 0) {
			return memo[month][ntv][npv];
		}
		
		int min = 100000;
		int mini = -1;
		for (int i = 0 ; i < len ; i++) {
			if ((ntv >= tv[i] && npv >= pv[i]) || (ntv < tv[i] - 1 || npv < pv[i] - 1)) {
				continue;
			}
			if (month >= exp[i]) {
				continue;
			}
			int ttv = Math.max(ntv, tv[i]);
			int tpv = Math.max(npv, pv[i]);
			int rec = dfs(month+1, ttv, tpv) + 1;
			if (min > rec) {
				min = rec;
				mini = i;
			}
		}
		memo[month][ntv][npv] = min;
		memo_prev[month][ntv][npv] = mini;
		
		return min;
	}
	
	public int[] getOrder(int[] t, int[] p, int[] expire, int sb) {
		bound = sb;
		tv = t;
		pv = p;
		exp = expire;
		len = tv.length;
		for (int i = 0 ; i < 51 ; i++) {
			for (int j = 0 ; j < 51 ; j++) {
				Arrays.fill(memo[i][j], -1);
				Arrays.fill(memo_prev[i][j], -1);
			}
		}
		
		int num = dfs(0, 0, 0);
		if (num >= 1000) {
			return new int[]{};
		}
		
		int nowmonth = 0;
		int nowtv = 0;
		int nowpv = 0;
		List<Integer> takecourse = new ArrayList<Integer>();
		while (nowtv < sb || nowpv < sb) {
			int c = memo_prev[nowmonth][nowtv][nowpv];
			takecourse.add(c);
			nowmonth++;
			nowtv = Math.max(nowtv, tv[c]);
			nowpv = Math.max(nowpv, pv[c]);
		}
		int[] ret = new int[takecourse.size()];
		for (int i = 0 ; i < ret.length ; i++) {
			ret[i] = takecourse.get(i);
		}
		return ret;
	}
}