POJ1742

Posted on | In ,

Coins

Solution sketch

有限背包問題，但是正常做會TLE QQ！（原理請看解說)

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstring>
bool ok[111111];
int used[111111];
int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && (n || m)) {
        int val[n], cnt[n];
        for (int i = 0; i < n; i++)
            scanf("%d", &val[i]);
        for (int i = 0; i < n; i++)
            scanf("%d", &cnt[i]);
        memset(ok, 0, sizeof(ok));
        ok[0] = true;
        for (int i = 0; i < n; i++) { // 對於所有的硬幣種類一個一個看
            memset(used, 0, sizeof(used));
            for (int j = 0; j <= m - val[i]; j++) { // 上限訂定為至少用一個硬幣的價值
                int next = j + val[i];
                // 如果目前這個數字已經可以湊出來，且還有剩餘的第i種硬幣可用，且利用一個第i種硬幣的那個值還未組出
                if (ok[j] == true && cnt[i] - used[j] > 0 && next <= m &&
                    ok[next] == false) {
                    ok[next] = true;
                    used[next] = used[j] + 1;  // 用一個硬幣掉
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            if (ok[i] == true)
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}