AOJ 0154 Sum of Cards
方針
メモ化再帰.
主に下準備で面倒くさいコードになってしまいました.
コード
int memo[8][1024]; struct card { int value; // 値 int resid; // 残数 card(int a, int b) : value(a), resid(b) {} }; void input(int m, vector<card>& cards) { int a, b; for(int i = 0; i < m; i++) { cin >> a >> b; card c(a, b); cards.push_back(c); } } int dfs(int p, int s, int& sum, int &m, vector<card>& cards) { if(s > 1000) return 0; if(p == m) return s == sum; if(memo[p][s] > 0) return memo[p][s] - 1; int res = 0; for(int i = 0; i <= cards[p].resid; i++) res += dfs(p + 1, s + cards[p].value * i, sum, m, cards); memo[p][s] = res + 1; return res; } int main() { int n, m, s; while(cin >> m, m) { vector<card> cards; input(m, cards); cin >> n; for(int i = 0; i < n; i++) { cin >> s; memset(memo, 0, sizeof memo); cout << dfs(0, 0, s, m, cards) << endl; } } }