Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-19SRM370 (Practice)

SRM 370 ConnectTheCities

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

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

  • dp[使った数][前回の位置][最大距離]で考えてみたがWA
    • 距離を決め打ちし二分探索するのが正解らしい
    • あとでちゃんと通す
  • 直した。
    • DPでも通る。終端の処理が間違ってた。
import java.util.Arrays;

public class ConnectTheCities {
	public int minimalRange(int distance, int funds, int[] position) {
		Arrays.sort(position);
		int len = position.length;
		
		int[][][] dp = new int[len+1][distance+1][distance+1];
		for (int i = 0 ; i <= len ; i++) {
			for (int pos = 0 ; pos <= distance ; pos++) {
				Arrays.fill(dp[i][pos], Integer.MAX_VALUE);
			}
		}
		dp[0][0][0] = 0;
		
		for (int i = 0 ; i < len ; i++) {
			for (int pos = 0 ; pos <= distance ; pos++) {
				for (int mxdist = 0 ; mxdist <= distance ; mxdist++) {
					if (dp[i][pos][mxdist] == Integer.MAX_VALUE) {
						continue;
					}
					for (int go = pos ; go <= distance ; go++) {
						int money = Math.abs(go - position[i]);
						int dist = mxdist;
						if (go >= pos) {
							dist = Math.max(go - pos, mxdist);
						}
						dp[i+1][go][dist] = Math.min(dp[i+1][go][dist], dp[i][pos][mxdist] + money);
					}
				}
			}
		}

		int dost = distance;
		for (int pos = 0 ; pos <= distance ; pos++) {
			for (int mxdist = 0 ; mxdist <= distance ; mxdist++) {
				if (dp[len][pos][mxdist] <= funds) {
					dost = Math.min(Math.max(distance - pos, mxdist), dost);
				}
			}
		}
		return dost;
	}

}