# 11068: 【原1068】小X的邮票

### 题目描述

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

## Description

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。

## Input Format

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

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

## Output Format

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

## 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;

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() {
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;
}