SRM609 Div2 Hard "VocaloidsAndSongs"
問題
TopCoder Statistics - Problem Statement
訳
ボーカロイドのグミ・イア・マユは歌うことが大好きだ。彼女らはS曲入っているアルバムをリリースすることにした。S個のそれぞれの曲は3人の内、少なくとも1人は担当する必要がある。それさえ守れば、1つの曲を2人、または3人同時に歌ってもよい。グミ・イア・マユの歌った曲の数はそれぞれ、gumi, ia, mayuである。
担当するボーカロイドの組み合わせが異なれば、それらは異なるアルバムである、としたときに、アルバムの作り方の数を返せ。
制約
1 <= S <= 50
1 <= gumi, ia, mayu <= S
考えたこと
グミしか知らない・・・
典型的なdp問題。もしくはメモ化再帰。何も考えずにコーディング!
dp[song][gumi][ia][mayu] := song個の曲をそれぞれのボーカロイドがgumi, ia, mayu だけ歌ったときの作り方の数
dp[0][0][0][0] = 1;
dp[S][G][I][E](S = G + I + E)の総和が答え
ソースコード
int N; int MOD = 1000000007; long long memo[55][55][55][55]; class VocaloidsAndSongs { public: long long dfs(int id, int rg, int ri, int rm){ if (id == N) { if (rg == 0 && ri == 0 && rm == 0) { return 1; } else { return 0; } } if (memo[id][rg][ri][rm] != -1) return memo[id][rg][ri][rm]; long long res = 0; // rem... if (rg == 0 && ri == 0 && rm == 0) { return 0; } // g if (rg > 0) { res += dfs(id + 1, rg - 1, ri, rm); res %= MOD; } // i if (ri > 0) { res += dfs(id + 1, rg, ri - 1, rm); res %= MOD; } // m if (rm > 0) { res += dfs(id + 1, rg, ri, rm - 1); res %= MOD; } // g i if (rg > 0 && ri > 0) { res += dfs(id + 1, rg - 1, ri - 1, rm); res %= MOD; } // g m if (rg > 0 && rm > 0) { res += dfs(id + 1, rg - 1, ri, rm - 1); res %= MOD; } // i m if (ri > 0 && rm > 0) { res += dfs(id + 1, rg, ri - 1, rm - 1); res %= MOD; } // g i m if (rg > 0 && ri > 0 && rm > 0) { res += dfs(id + 1, rg - 1, ri - 1, rm - 1); res %= MOD; } return memo[id][rg][ri][rm] = res; } int count(int S, int gumi, int ia, int mayu) { N = S; memset(memo, -1, sizeof(memo)); return dfs(0, gumi, ia, mayu); } };