Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-25SRM362, SRM363 (Practice)

SRM 363 HandsShaking

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

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

  • メモ化再帰するだけ。簡単。
public class HandsShaking {
	long[] memo = new long[100];
	
	public long dfs(int n) {
		if (n <= 4) {
			return memo[n];
		}
		if (memo[n] >= 1) {
			return memo[n];
		}
		
		long ans = 0;
		int left = n - 2;
		for (int z = 0 ; z <= left ; z += 2) {
			ans += dfs(left-z) * dfs(z);
		}
		memo[n] = ans;
		return ans;
	}
	
	public long countPerfect(int n) {
		memo[0] = 1;
		memo[2] = 1;
		memo[4] = 2;
		return dfs(n);
	}
}