不算难，注意 base case是 cur == S，cur表示当前已经唱了的歌曲数。
代码:
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) /*************** Program Begin **********************/ int dp[51][51][51][51]; int d1[] = {1, 0, 1, 0, 1, 0, 1}; int d2[] = {0, 1, 1, 0, 0, 1, 1}; int d3[] = {0, 0, 0, 1, 1, 1, 1}; const int MOD = 1e9 + 7; class VocaloidsAndSongs { public: int S, gumi, ia, mayu; int rec(int cur, int v1, int v2, int v3) { if (cur == S) { if (v1 == gumi && v2 == ia && v3 == mayu) { return 1; } else { return 0; } } int & res = dp[cur][v1][v2][v3]; if (res != -1) { return res; } res = 0; for (int i = 0; i < 7; i++) { int t1 = v1 + d1[i]; int t2 = v2 + d2[i]; int t3 = v3 + d3[i]; if (t1 > gumi || t2 > ia || t3 > mayu) { continue; } else { res += rec(cur + 1, t1, t2, t3); res %= MOD; } } return res; } int count(int S, int gumi, int ia, int mayu) { this->S = S; this->gumi = gumi; this->ia = ia; this->mayu = mayu; memset(dp, -1, sizeof(dp)); return rec(0, 0, 0, 0); } }; /************** Program End ************************/