游客 注册 | 登录
中文 | En

3244 - 量取

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

星哥要量取Q (1≤Q≤20000)体积的清水，把它倒进自己的游泳池中。

星哥向来节约。为了量出Q体积的水，他必须去商店里买一些称量用的提桶。由于每个桶的价格是一样的，你的任务就是帮星哥计算为了量出Q体积的水，最少要买哪一些提桶。由于星哥必须把这些东西搬回家，所以对于任意两个最少数量的候选方案，他会偏向“更小”一组，即把两组解按升序排列，比较第一个桶的容积，选择容积小的一组。如果排在第一的两个桶容积相同，就比较第二个，一直继续这样的工作，直到找到两个桶的容积不一致为止，例如{3,5,7,100} 比 {3,6,7,8} 要好。

       量水时，星哥会用把提桶装满，然后倒进池子，他决不会把已经在一个桶里的水倒到别的桶里去。如果星哥有一个容积为1的桶，他可以只用这个桶量出所有的份量，但如果他遇到的是其它的组合就不会这么方便了。我们保证所有的测试数据至少有一个解，试确定购买的最优方案。

题目输入

第一行：单个整数Q 
第二行：单个整数P (1≤P≤100)表示商店里提桶的数量 
第三行到第P+2行：每行只有一个整数，表示某个提桶的容积 (1≤容积≤10000)

题目输出

输出文件只有一行，由空格分开的整数组成，包括： 
    为了量出指定的体积，需要购买的提桶的最少数量，其次是一个以升序排列的序列，表示需要购买的每个提桶的容积

输入/输出样例

输入格式

16
3
3
5
7

输出格式

2 3 5

C++解答

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int m,n,k,v,tot;
int a[221],ans[221];
int many[20005],which[20005],pre[20005];
void init();
void work();
int main()
{
	//freopen("water.in","r",stdin);
	//freopen("water.out","w",stdout);
	init();
	work();
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}
void init()
{
	cin>>v;
	for(int i=1;i<=v;i++) many[i]=2000;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
}
void work()
{
	int t;
	many[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=v-a[i];j++)
			if(many[j]!=2000 && which[j]!=a[i])
			for(int k=1;k<=(v-j)/a[i];k++)
			{
				t=a[i]*k+j;
				if(many[j]+1==many[t])
					if(which[j]<which[pre[t]])
					{
						which[t]=a[i];
						pre[t]=j;
					}
				if(many[j]+1<many[t])
				{
					many[t]=many[j]+1;
					which[t]=a[i];
					pre[t]=j;
				}
			}
		cout<<many[v];
		t=v;
		while(t!=0)
		{
			tot++;
			ans[tot]=which[t];
			t=pre[t];
		}
		for(int i=tot;i>0;i--) cout<<' '<<ans[i];
}
请先登陆