Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-15SRM300台を練習していく part9

SRM 325 FenceRepairing

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

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

DPするだけ。div1easyとだけあって簡単。

300だが恐るるに足らず。


public class FenceRepairing {

	public String _bd;
	public int _l;
	
	public double[] memo;
	
	
	public double dfs(int idx) {
		if (idx >= _l - 1) {
			return 0.0d;
		}
		if (idx >= 0) {
			if (memo[idx] >= 0.0d) {
				return memo[idx];
			}
		}
		
		double mincost = -1;
		int from = idx;
		for (int i = from + 1 ; i < _l ; i++) {
			if (_bd.charAt(i) == '.') {
				from++;
			} else {
				break;
			}
		}
		
		for (int i = idx + 1 ; i < _l ; i++) {
			if (_bd.charAt(i) == 'X') {
				double cost = Math.sqrt(i - from) + dfs(i);
				if (mincost < 0 || mincost > cost) {
					mincost = cost;
				}
			}
		}
		if (mincost < 0) {
			mincost = 0;
		}
		if (idx >= 0) {
			memo[idx] = mincost;
		}
		return mincost;
	}
	
	
	public double calculateCost(String[] boards) {
		String board = "";
		for (String b : boards) {
			board += b;
		}
		
		_l = board.length();
		_bd = board;
		memo = new double[5000];
		java.util.Arrays.fill(memo, -1.0d);
		
		int start = -1;
		for (; start < _l - 1 ; start++) {
			if (_bd.charAt(start+1) == 'X') {
				break;
			}
		}
		return dfs(start);
	}
}