记录编号	317042	评测结果	AAAAAAAAAA
题目名称	量取牛奶	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	1.763 s
提交时间	2016-10-07 16:49:35	内存使用	25.48 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("milk4.in","r",stdin);freopen("milk4.out","w",stdout);chul();Cu;
using namespace std;
const int maxn=20010;
int f[110][maxn];
int pre1[110][maxn],pre2[110][maxn],w[110];
void chul(){
	int q,p,n;
	scanf("%d%d",&q,&p);
	for(int i=1;i<=p;i++)scanf("%d",&w[i]);
	sort(w+1,w+1+p);
	n=p;
	for(int i=1;i<=p;i++){
		if(w[i]==w[i-1]){
			w[i]=0x7f7f7f7f;
			n--;
		}
	}
	memset(f,0x7f,sizeof(f));
	f[0][0]=0;
	sort(w+1,w+1+p);
	int ans1=200,ans2[110],ans3[110];
	for(int i=1;i<=n;i++){
		for(int j=w[i];j<=q;j++){
			for(int m=0;m<i;m++){
				for(int k=1;k*w[i]<=j;k++){
					if(f[i][j]>=f[m][j-k*w[i]]+1){
						f[i][j]=f[m][j-k*w[i]]+1;
						pre1[i][j]=m;
						pre2[i][j]=k;
						if(j==q){
							if(f[i][j]<ans1){
								ans1=f[i][j];
								int x=i,y=j;
								ans2[0]=0;
								while(x!=0){
									int tim=y;
									ans2[++ans2[0]]=x;
									y=y-pre2[x][y]*w[x];
									x=pre1[x][tim];
								}
								reverse(ans2+1,ans2+1+ans2[0]);
								ans2[ans2[0]+1]=0x7f7f7f7f;
							}
							else if(f[i][j]==ans1){
								int x=i,y=j;
								ans3[0]=0;
								while(x!=0){
									int tim=y;
									ans3[++ans3[0]]=x;
									y=y-pre2[x][y]*w[x];
									x=pre1[x][tim];
								}
								reverse(ans3+1,ans3+1+ans1);
								bool flag=1;
								for(x=1;x<=ans1;x++){
									if(ans3[x]<ans2[x]){
										flag=0;
										break;
									}
								}
								if(!flag){
									for(x=0;x<=ans1;x++){
										ans2[x]=ans3[x];
									}
								}
							}
						}
					}
				}
			}
		}
	}
	printf("%d ",ans1);
	for(int i=1;i<=ans1;i++)printf("%d ",w[ans2[i]]);
}
int main(){
	Begin;
}