HDUOJ 2844 Coins

Posted on Edited on In

原题：POJ 1742 Coins

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 101, M = 100001;
int n, m, w[N], s[N], num[M], f[M], ans;
int main() {
    while (scanf("%d%d", &n, &m), n) {
        for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
        for (int i = 1; i <= n; ++i) scanf("%d", &s[i]);
        memset(f, false, sizeof(f));
        f[0] = true;
        ans = 0;
        for (int i = 1; i <= n; ++i) {
            memset(num, 0, sizeof(num));
            for (int j = w[i]; j <= m; ++j)
                if (!f[j] && f[j - w[i]] && num[j - w[i]] < s[i]) {
                    f[j] = true;
                    num[j] = num[j - w[i]] + 1;
                    ++ans;
                }
        }
        printf("%d\n", ans);
    }
    return 0;
}