メモ

自分に向けて書いたメモを取り扱っています.

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;
        }
    }
}