(背包) $O(nm)$

在阶段 i 时,F [j] 表示前 i 种硬币能否组成面值 j .
used[j] 表示 F[j] 在阶段 i 时为true至少需要多少枚第 i 种硬币.
所以在 F[j - a[i]] 为真, F[j] 却为假的时候, F[j] 为真的状态由 F[j - a[i]] 转移而来,这个时候 used[j] = used[j - a[i]] + 1.
最后只需要看有多少个值的状态为真,那么就知道有多少种面值了.

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 105;
const int M = 1e5 + 10;
int a[N],c[N];
int f[M],used[M];


int main()
{
    ios::sync_with_stdio(false);

    int n,m;

    for ( ; ; )
    {
        int ans = 0;

        cin >> n >> m;
        if ( n == 0 && m == 0) break;

        for (int i = 1; i <= n; ++ i ) cin >> a[i];
        for (int i = 1; i <= n; ++ i ) cin >> c[i];

        memset(f,0,sizeof(f));
        memset(used,0,sizeof(used));

        f[0] = 1;

        for (int i = 1; i <= n; ++ i )
        {
            for (int j = 0; j <= m; ++ j ) used[j] = 0;
            for (int j = a[i]; j <= m; ++ j )
            {
                if (!f[j] && used[j - a[i]] < c[i] && f[j - a[i]])
                    f[j] = true, used[j] = used[j - a[i]] + 1;
            }
        }

        for (int i = 1; i <= m; ++ i )
            if (f[i]) ++ans;

        cout << ans << endl;
    }

    return 0;
}