SRM 349 Div1 Medium DiceGames

問題

目の数が異なるサイコロが複数与えられる。各サイコロの目の数はsides[]である。サイコロを一斉に降った時に、サイコロを区別しないとして出る目のパターン数を求めよ。

やりかた

サイコロを目の数でソートしてDP。
dp[i][j]:=（サイコロを目の数の小さい方からi番目まで見た時にi番目の目がjであるときのパターン数）

イメージ

以下ソース。

class DiceGames {
public:
  long long countFormations(vector <int> sides){
    sort(ALL(sides));
    int N = sides.size();
    vector<vector<ll>> dp(N + 1, vector<ll>(33, 0));
    
    for(int i = 1; i <= sides[0]; i++) dp[0][i] = 1;
    
    for(int i = 0; i + 1 < N; i++)
      for(int j = 1; j <= sides[i]; j++)
	for(int k = j; k <= sides[i + 1]; k++)
	  dp[i + 1][k] += dp[i][j];

    ll ans = 0;
    for(int i = 1; i <= 32; i++) ans += dp[N - 1][i];
    return ans;
  }
};