Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-04SRM349 (Practice)

SRM 349 DiceGames

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

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

  • ソートして数え上げるだけ
    • メモ化再帰を実装した
import java.util.Arrays;

public class DiceGames {
	
	int[] a;
	int len;
	
	long[][] memo;
	
	public long dfs(int i, int prev) {
		if (i == len) {
			return 1;
		}
		if (memo[i][prev] >= 0) {
			return memo[i][prev];
		}
		
		long ret = 0;
		for (int n = prev ; n <= a[i] ; n++) {
			ret += dfs(i+1, n);
		}
		memo[i][prev] = ret;
		return ret;
	}

	public long countFormations(int[] sides) {
		a = sides;
		len = sides.length;
		Arrays.sort(sides);
		
		memo = new long[50][50];
		for (int i = 0 ; i < 50 ; i++) {
			Arrays.fill(memo[i], -1);
		}
		return dfs(0, 1);
	}
}