Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

SRM 323 RoadsAndFools

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

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

散々悩んだ挙句、普通にDPして何通りあるか数えることにした。

2通り以上か0通りだったら終わり。

1通りの場合、ある箇所が逆順になっていたら、どちらかを全長から引いて、を繰り返してsequenceを求める。


public class RoadsAndFools {
	int[] _f;
	int _l;
	int _ll;
	int _ans = 0;
	
	int[][] memo = new int[51][1002];
	
	public int dfs(int a, int now) {
		if (a >= _l - 1) {
			return 1;
		}
		if (memo[a][now] >= 1) {
			return memo[a][now];
		}

		int ret = 0;
		if (now < _f[a+1]) {
			ret += dfs(a+1, _f[a+1]);
		}
		if (now < _ll - _f[a+1] && _f[a+1] != _ll - _f[a+1]) {
			ret += dfs(a+1, _ll - _f[a+1]);
		}
		memo[a][now] = ret;
		
		return ret;
	}
	
	public String determineOrientation(int length, int[] frontSides) {
		int len = frontSides.length;
		_l = len;
		_f = frontSides;
		_ll = length;

		int a = dfs(0, _f[0]);
		if (_ll - _f[0] != _f[0]) {
			a += dfs(0, _ll - _f[0]);
		}
		
		if (a >= 2) {
			return "MULTIPLE SOLUTIONS";
		}
		if (a == 0) {
			return "NO SOLUTION";
		}
		
		String answer = "";
		for (int i = 0 ; i < len - 1 ; i++) {
			if (_f[i] >= _f[i+1]) {
				_f[i] = _ll - _f[i];
				if (_f[i] >= _f[i+1]) {
					_f[i] = _ll - _f[i];
					_f[i+1] = _ll - _f[i+1];
				}
			}
			answer = answer + _f[i] + " ";
		}
		answer += _f[len-1];
		
		return answer;
	}
}