Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-22SRM366 (Practice)

SRM 366 ChangingSounds

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

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

  • [現在位置][音量]でDPする
    • 50 * 1000 = 50,000
  • 書いた。サンプル通った。
    • これはスピード勝負な気がするのでそのまま出した。
public class ChangingSounds {

	public int maxFinal(int[] ci, int beginLevel, int maxLevel) {
		int len = ci.length;
		boolean[][] dp = new boolean[len+1][maxLevel+1];
		dp[0][beginLevel] = true;
		for (int i = 0 ; i < len ; i++) {
			for (int l = 0 ; l <= maxLevel ; l++) {
				if (dp[i][l]) {
					int[] to = {l - ci[i], l + ci[i]};
					for (int d = 0 ; d <= 1 ; d++) {
						if (0 <= to[d] && to[d] <= maxLevel) {
							dp[i+1][to[d]] = true;
						}
					}
				}
			}
		}
		
		int max = -1;
		for (int l = 0 ; l <= maxLevel ; l++) {
			if (dp[len][l]) {
				max = Math.max(max, l);
			}
		}
		return max;
	}
}