题目描述

$ 在阶段i时,f(j)表示前i种硬币是否能组合成面值j, cnt(j)表示f(j)为真时至少需要多少$

$枚第i种硬币。所以在f(i - a_i)为真,f(j)为假时,f(j)为真的状态由f(i - a_i)$

$转移过来，这个时候cnt(j) = cnt(j - a_i) + 1.由于每个物品可以多次选取，$

$所以j应该正序枚举。$

$ 最后只需要看有多少个f(j)的状态为真，就知道有多少种面值了。$

样例

样例输入

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

样例输出

8
4

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n, m;
int a[N], c[N], f[N];
int main(){
    while(cin >> n >> m, n || m){
        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));

        f[0] = 1;
        int st[N];
        for(int i = 1;i <= n;i ++){
            for(int j = 0;j < m;j ++) st[j] = 0;
            for(int j = a[i];j <= m;j ++)
                if(!f[j] && f[j - a[i]] && st[j - a[i]] < c[i])
                    f[j] = 1, st[j] = st[j - a[i]] + 1;
        }
        int ans = 0;
        for(int i = 1;i <= m;i ++)
            if(f[i]) ans ++;
        printf("%d\n", ans);
    }
    return 0;
}