再见H胖胖
时间: 1ms 内存:128M
描述:
听H胖胖说H胖胖学长叨扰大家一年了,甚是内疚,于是H胖胖学长给大家买了一个礼物,给大家这两个学期的c语言程序设计画上圆满的句号。H胖胖学长看了看自己的口袋,有n个面值为a1,a2……an的金币各一枚,H胖胖学长想知道自己为了买这个礼物他的哪些硬币是必须被使用的,即H胖胖学长必须使用哪些金币。卖家不找零,只能恰好的金币总数。(本次为代码填空题,代码见提示,如果大家不用提示代码,欢迎大家自己尝试编写)提交全部代码,不是只有填空部分!
输入:
第一行是两个个整数n,x。(1 <= n <= 200,1<=x<=10000)。
第二行从小到大为n个整数a1,a2......an(1<=ai<=x)
输出:
第一行是一个整数,有多少个金币必须被使用的。
第二行是这些必须被使用的金币的面值(从小到大排列)。
注:输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付X元。
如果不存在必须被使用的硬币,则第一行输出0,第二行输出空行。
示例输入:
5 18
1 2 3 5 10
示例输出:
2
5 10
提示:
参考答案(内存最优[2024]):
#include<iostream>
#include<cstring>
using namespace std;
const int MAXPRICE = 10002; //最大物品价值
const int MAXN = 202; //最大数量的金币个数
int main(){
int dp[MAXPRICE]; //dp[j]表示价格为j的物品有几种面值的金币组成
int coin[MAXN]; //coin[j]表示第j个金币的面值
int unique[MAXN]; //unique[j]表示第j个必须使用金币的面值
int ans[MAXPRICE]; //ans[j]表示dp[j]去掉某个金币的面值之后有几种面值的金币组成
memset(dp,0,sizeof(dp)); //初始化dp数组所有值为0
dp[0] = 1;
int n,x;
int cnt = 0;
cin >> n >> x;
for(int i = 1 ; i <= n ; i++) //输入每个金币的面值,从1开始
cin >> coin[i];
for(int i = 1; i <= n ; i++)
for(int j = x ; j >= coin[i] ; j--) //组成价格为x的物品有几种面值的金币组成
dp[j] += dp[j-coin[i]];
for(int i = 1 ; i <= n ; i++){
for(int j = 0 ; j <= x ; j++)
if(j < coin[i])
ans[j] = dp[j];
else
ans[j] = dp[j] - ans[j-coin[i]];
if(ans[x] == 0)
unique[cnt++] = coin[i];
}
cout << cnt << endl;
if(cnt > 0){
for(int i = 0 ; i < cnt ; i++)
if(i < cnt - 1 )
cout << unique[i] << " ";
else
cout << unique[i] << endl;
}else{
cout << endl;
}
return 0;
}
参考答案(时间最优[3]):
#include<iostream>
#include<cstring>
using namespace std;
const int MAXPRICE = 10002; //最大物品价值
const int MAXN = 202; //最大数量的金币个数
int main(){
int dp[MAXPRICE]; //dp[j]表示价格为j的物品有几种面值的金币组成
int coin[MAXN]; //coin[j]表示第j个金币的面值
int unique[MAXN]; //unique[j]表示第j个必须使用金币的面值
int ans[MAXPRICE]; //ans[j]表示dp[j]去掉某个金币的面值之后有几种面值的金币组成
memset(dp,0,sizeof(dp)); //初始化dp数组所有值为0
dp[0] = 1;
int n,x;
int cnt = 0;
cin >> n >> x;
for(int i = 1 ; i <= n ; i++) //输入每个金币的面值,从1开始
cin >> coin[i];
for(int i = 1; i <= n ; i++)
for(int j = x ; j >= coin[i] ; j--) //组成价格为x的物品有几种面值的金币组成
dp[j] += dp[j-coin[i]];
for(int i = 1 ; i <= n ; i++){
for(int j = 0 ; j <= x ; j++)
if(j < coin[i])
ans[j] = dp[j];
else
ans[j] = dp[j] - ans[j-coin[i]];
if(ans[x] == 0)
unique[cnt++] = coin[i];
}
cout << cnt << endl;
if(cnt > 0){
for(int i = 0 ; i < cnt ; i++)
if(i < cnt - 1 )
cout << unique[i] << " ";
else
cout << unique[i] << endl;
}else{
cout << endl;
}
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。