简答题
偏难
#7464
硬币(2024.3四级) 宇航员 Bob 有一天来到火星上, 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了, 一共有 n 种, 每种只有一个:…
硬币(2024.3四级)
宇航员 Bob 有一天来到火星上, 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了, 一共有 n 种, 每种只有一个: 面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物, 想买来送给朋友 Alice, 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的, 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零, 只接受恰好 X 元。
时间限制: 1000
内存限制: 262144
输入
第一行包含两个正整数 n 和 x。 (1 <= n <= 200, 1 <= x <= 10000)
第二行从小到大为 n 个正整数 a1, a2, a3 … an (1 <= ai <= 10000)
输出
第一行是一个整数, 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值(从小到大排列) 。
样例输入
5 18 1 2 3 5 10
样例输出
2 5 10
提示
输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币, 则第一行输出 0, 第二行输出空行。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
using namespace std;
int val[210] = {0};
int ways[10000] = {0};
int ans[210] = {0};
int cal(int x, int y) {
if (x < 0)
return 0;
return ways[x] - cal(x - y, y);
}
int main() {
int N, Max;
cin >> N >> Max;
for (int i = 1; i <= N; ++i)
cin >> val[i];
ways[0] = 1;
for (int i = 1; i <= N; ++i)
for (int j = Max; j >= val[i]; --j)
ways[j] += ways[j - val[i]];
int cnt = 0;
for (int i = 1; i <= N; ++i)
if (cal(Max, val[i]) == 0)
ans[cnt++] = val[i];
cout << cnt << endl;
if (cnt == 0)
cout << ' ' << endl;
else {
cout << ans[0];
for (int i = 1; i < cnt; ++i)
cout << ' ' << ans[i];
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。