Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-06SRM300台を練習していく part8

SRM 320 ContestSchedule

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

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

コンテストを終わりの早い順に並び替え、DPするだけ


import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ContestSchedule {

	
	class Contest {
		long s, e;
		double p;
		public Contest(String[] param) {
			s = Long.valueOf(param[0]);
			e = Long.valueOf(param[1]);
			p = Integer.valueOf(param[2]) * 1.0d / 100;
		}

		public String toString() {
			return s + "-" + e + ":" + p;
		}
	}
	
	List<Contest> conts = new ArrayList<Contest>();
	
	Map<Integer, Map<Long, Double>> memo = new HashMap<Integer, Map<Long, Double>>();
	
	public double dfs(int i, long time) {
		double ans = 0.0d;
		if (i >= conts.size()) {
			return ans;
		}
		if (memo.get(i).containsKey(time)) {
			return memo.get(i).get(time);
		}
		
		Contest c = conts.get(i);
		
		ans = dfs(i+1, time);
		if (time <= c.s) {
			ans = Math.max(ans, dfs(i+1, c.e) + c.p);
		}
		memo.get(i).put(time, ans);
		
		return ans;
	}
	
	
	public double expectedWinnings(String[] contests) {
		int len = contests.length;
		for (String cont : contests) {
			conts.add(new Contest(cont.split(" ")));
		}
		java.util.Collections.sort(conts, new Comparator<Contest>() {
			public int compare(Contest a, Contest b) {
				return (int)(a.e - b.e);
			}
		});
		for (int i = 0 ; i <= len ; i++) {
			memo.put(i, new HashMap<Long, Double>());
		}
		
		return dfs(0, 0);
	}

}