记录编号	266669	评测结果	AAAAAAAAAA
题目名称	量取牛奶	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2016-06-08 23:20:18	内存使用	0.12 MiB

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
bool flag[20010]={0};
int f[20010]={0},v[210]={0},p[20010][3]={0},ans[210]={0};
int cmp(const void*a,const void*b)
{
	return *(int*)a-*(int*)b;
}
int _521()
{
	freopen("milk4.in","r",stdin);
	freopen("milk4.out","w",stdout);
	int i,j,k,m,n;
	scanf("%d%d",&m,&n);
	for(i=1;i<=n;i++) scanf("%d",v+i);
	qsort(v+1,n,sizeof(v[0]),cmp);
	memset(f,127,sizeof(f));
	flag[0]=1;f[0]=0;
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=m;j++)
		if(flag[j])
		for(k=j+v[i];k<=m;k+=v[i])
		{
			flag[k]=1;
			if(f[k]>f[j]+1)
			  f[k]=f[j]+1,p[k][0]=v[i],p[k][1]=i,p[k][2]=j;
			else if(f[k]==f[j]+1&&p[j][1]<p[p[k][2]][1])
			  p[k][0]=v[i],p[k][1]=i,p[k][2]=j;
		}
	}
	printf("%d",f[m]);
	i=0;
	while(m) ans[++i]=p[m][0],m=p[m][2];
	while(i) printf(" %d",ans[i--]);
	return 0;
}
int _520=_521();
int main(){;}