题目描述:

今天天气好晴朗，处处好风光，好风光！蝴蝶儿忙啊，蜜蜂也忙，信息组的同学们更加忙。最近，由于XX原因，大家不得不到岳麓山去提水。55555555~，好累啊。 信息组有一个容量为q升的大缸，由于大家都很自觉，不愿意浪费水，所以每次都会刚好把缸盛满。但是，信息组并没有桶子（或者瓢）来舀水，作为组内的生活委员，你必须肩负重任，到新一佳去买桶子。 新一佳有p种桶子，每种桶子都有无穷多个_，且价钱一样。由于大家都很节约，所以你必须尽量少买桶子。如果有多种方案，你必须选择“更小”的那种方案，即：把这两个方案的集合（不同大小的桶子组成）按升序排序，比较第一个桶，选择第一个桶容积较小的一个。如果第一个桶相同，比较第二个桶，也按上面的方法选择。否则继续这样的比较，直到相比较的两个桶不一致为止。例如，集合{3，5，7，三} 比集合 {3，6，7，8} 要好。 为了把缸装满水，大家可以先从岳麓山的井里把桶装满水提回来，然后倒进缸里。为了不十分麻烦或者浪费宝贵的水资源，大家决不把缸里的水倒出来或者把桶里的水倒掉，也不会把桶里的水再倒回井中，（这样会污染井水）。当然，一个桶可以使用多次。例如，用一个容积为 1 升的桶可以将任意容量的大缸装满水。而其它的组合就要麻烦些。ps:什么鬼畜背景

输入格式

第1行1个数q(q<=20000)。 第2行1个数p(p<=100)。 接下来p行，每行一个数，依次为每个桶的容积。

输出格式

共1行，每两个数间用空格分隔，第1个数k为最少的桶的数量，接下来k个数从小到大输出每个桶的容量。

样例输入

16

3

3

5

7

样例输出

2 3 5

1

2 3 5

迭代加深搜索：这篇文章写得不错，我自己也还需要多多理解。题意：给几个数，用最少的数组合成目标数，字典序最小。有点像dfs和完全背包的结合。某谷上这道题可以用同一份代码a过又是本蒟蒻刷ac率的好机会了。

代码：

#include<bits/stdc++.h>#define read read()using namespace std;int read {int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*=f;}int n,m,ub;int v[105],ans[105],ex[20005];bool judge(int l)//l即left：判断剩下的缸容积是否可以用桶容积表示出来，即ex[l]=1{if(ex[l]!=-1) return ex[l];if(l==0) return ex[l]=1;for(int i=0;i<ub;i++)//用先前选择的桶能否表示出剩下的缸容积，注意i从0开始列举if(l>=ans[i]&&judge(l-ans[i])) return ex[l]=1;//本蒟蒻把ans打成v半天没看出来，过了6个点 return ex[l]=0;}void dfs(int tot,int now){if(now==ub)//若被选择的桶数达到预计{memset(ex,-1,sizeof(ex));if(judge(n)){printf("%d",ub);for(int i=0;i<ub;i++)printf(" %d",ans[i]);exit(0);//直接结束程序}return;}if(tot>=m) return;ans[now]=v[tot];//ans[now]储存被选择的第now个桶容积为v[tot]dfs(tot+1,now+1);//tot为枚举第几个桶，若选择该桶则now+1。now统计被选择的桶的种类数dfs(tot+1,now);}int main(){//freopen("in.txt","r",stdin);n=read;m=read;for(int i=0;i<m;i++){v[i]=read;}sort(v,v+m);//因为要求字典序最小，所以将桶的容积从小到大排序for(ub=1;ub<=m;ub++)//因为尽量用少的桶，所以从小到大列举预计要用的桶的种类数{dfs(0,0);}return 0;}

如果觉得《「vijos1159」岳麓山上打水/MZOJ1005: 打水》对你有帮助，请点赞、收藏，并留下你的观点哦！