TopCoder SRM 349 Div1 Medium DiceGames

問題

n個のダイスがあり、それぞれの面の数はsides[i]個である。
それぞれのダイスは1〜sides[i]の面を持つ。

これらのダイスをそれぞれ一度ずつ振り、出た目を順序を無視して扱う。
例えば、{1, 1, 2}と{1, 2, 1}は同じ出目として扱う。

出目は何通りあるか、求めよ。

制約条件

sides[i]≦32
n≦32

方針

動的計画法による。
ダイスA,BがあってAよりBの面のほうが多いとき、
たとえばAで5,Bで3の目が出たとする。
これは、Aで3、Bで5が出たとみなすことが出来る。

なので、ダイスを面の数の少ない順にソートして、
出目a,b,c,d...はa≦b≦c≦d...であるして数えてよい。

これは、dp[i][j]を、i番目のダイスまで使い、最後の出目がjであるような場合の数とするようなDPにより数えられる。

ソースコード

ll dp[50][50];

class DiceGames {
	public:
	long long countFormations(vector <int> sides) 
	{
		int n=sides.size();
		
		sort(all(sides));
		memset(dp,0,sizeof(dp));
		
		dp[0][0]=1;
		rep(i,n)rep(j,50)for(int k=max(1,j);k<=sides[i];k++)
			dp[i+1][k]+=dp[i][j];
		ll ans=0;
		rep(i,50)ans+=dp[n][i];
		return ans;
	}
};