Skip to content

11069: 【原1069】二哥的硬币

题目

题目描述

author: 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1069

Description

快放假了,二哥想给女朋友买一个礼物。

走到商店前,发现钱包里只有硬币了。二哥数了一下,一共有n种硬币,面值分别为A1, A2, ..., An,每种硬币的个数分别为C1, C2, ..., Cn。

二哥心里没有底,他估计要买的礼物价格不会超过m,但不知道到底要买多少钱的礼物。

二哥的硬币已经很多了,他不想再要更多的硬币了,所以他想知道,用手头这些硬币,可以正好凑出1到m中多少种金额(正好相等,包括1和m)。

Input Format

输入包含多组测试数据。

每组测试数据的第一行是空格分隔的两个整数n和m,\( 1 \leq n \leq 100,1 \leq m \leq 100000 \) 。

接下来有2n个整数,分别是面值A1, A2, ..., An,以及硬币个数C1, C2, ..., Cn,用空白分隔,\( 1 \leq Ai \leq 100000,1 \leq Ci \leq 1000 \) 。

当读入的n=0且m=0时,表示输入结束;这组数据不需要处理。

Output Format

对于每组测试数据,输出用这些硬币可以正好凑出1到m范围内的多少种金额。

说明

http://poj.org/problem?id=1742

Sample Input

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

Sample Output

4
8

FineArtz's solution

/* 二哥的硬币 */
#include <iostream>
#include <cstring>
using namespace std;

int a[100005], c[1005], f[100005];

void work(int n, int m){
    memset(a, 0, sizeof(a));
    memset(c, 0, sizeof(c));
    memset(f, -1, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i)
        cin >> c[i];
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j <= m; ++j){
            if (f[j] >= 0)
                f[j] = c[i];
            else if (j < a[i] || f[j - a[i]] < 0)
                f[j] = -1;
            else
                f[j] = f[j - a[i]] - 1;
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; ++i)
        if (f[i] >= 0)
            ++ans;
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    while (n != 0 || m != 0){
        work(n, m);
        cin >> n >> m;
    }
    return 0;
}

yyong119's solution

#include <cstdio>
#include <cstring>
#define MAX_N 105
#define MAX_M 100005
using namespace std;  

int n, m;
int w[MAX_N], c[MAX_N], sum[MAX_M], f[MAX_M];

int main() {

    while (~scanf("%d%d", &n, &m)) {

        if (n == 0 && m == 0)
            break;
        for (int i = 0; i < n; ++i)
            scanf("%d", &w[i]);
        for (int i = 0; i < n; ++i)
            scanf("%d", &c[i]);

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