11068: 【原1068】小X的邮票

题目

题目描述

author: 寿鹤鸣 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1068

Description

小X喜欢收集邮票，已知一个N枚邮票的面值集合（如，{ 1分，3分 }）和一个上限K-表示信封上能够贴K张邮票。计算从1到M的最大连续可贴出的邮资。例如，假设有1分和3分的邮票；最多可以贴5张邮票。很容易贴出1到5分的邮资（用1分邮票贴就行了），接下来的邮资也不难：

6 = 3 + 3 7 = 3 + 3 + 1 8 = 3 + 3 + 1 + 1 9 = 3 + 3 + 3 10 = 3 + 3 + 3 + 1 11 = 3 + 3 + 3 + 1 + 1 12 = 3 + 3 + 3 + 3 13 = 3 + 3 + 3 + 3 + 1。

然而，使用 5 枚 1 分或者 3 分的邮票根本不可能贴出 14 分的邮资。因此，对于这两种邮票的集合和上限 K=5，答案是 M=13。

Input Format

两个整数，K 和 N

K（ \(1 \leq K \leq 200\) ）是可用的邮票总数。

N（ \(1 \leq N \leq 50\) ）是邮票面值的数量。

Output Format

N 个整数，每行 15 个，列出所有的 N 个邮票的面值，面值不超过 10000。

Hint

Sample Input

5 2
1 3

Sample Output

13

FineArtz's solution

/* 小X的邮票 */
#include <iostream>
using namespace std;

int k, n, m = 0, ans = 0;
int a[205] = {0}, f[2000005] = {0};

int main(){
    cin >> k >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        f[a[i]] = 1;
        if (a[i] > m)
            m = a[i];
    }
    for (int i = 1; i <= m * k; ++i)
        if (f[i] == 0)
            f[i] = 500;
    ans = m * k;
    for (int i = 1; i <= m * k; ++i){
        for (int j = 1; j <= n; ++j){
            f[i + a[j]] = min(f[i + a[j]], f[i] + 1);
        }
        if (f[i] > k){
            ans = i - 1;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

yyong119's solution

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define MAX_N 55
#define MAX_K 205
#define MAX_VALUE 2000005
using namespace std;
queue<int> q;
bool d[MAX_VALUE];
int val[MAX_N];
int n, k;

inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = res * 10 + ch - '0', ch = getchar();
    return res;
}

int main() {
    k = read(); n = read();
    for (int i = 0; i < n; ++i) val[i] = read();
    q.push(0);
    for (int i = 1; i <= k; ++i) {
        int cnt = q.size();
        for (int x = 0; x < cnt; ++x) {
            int v = q.front(); q.pop();
            for (int j = 0; j < n; ++j) {
                int v_tmp = v + val[j];
                if (!d[v_tmp]) {
                    q.push(v_tmp);
                    d[v_tmp] = true;
                }
            }
        }
    }
    for (int i = 1; i < MAX_VALUE; ++i)
        if (!d[i]) {
            printf("%d\n", i - 1);
            break;
        }
    return 0;
}