题目链接

Coins POJ - 1742

思路

$$ dp[j]表示a[i]在j位置后可以放几个 $$

时间复杂度

$$ O(NM) $$

代码

#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 1e5 + 10;
int a[MAXN], b[MAXN], dp[MAXN];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m), n + m) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);// don't forget &
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);// don't forget &
        }
        memset(dp, -1, sizeof dp);
        dp[0] = 0;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (dp[j] != -1) {
                    dp[j] = b[i];
                } else {
                    if (j - a[i] >= 0 && dp[j - a[i]] > 0) {
                        ans++;
                        dp[j] = dp[j - a[i]] - 1;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}