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

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

int i,N,Q,n;

bool flag=0;

const int maxn=110;

int Ans[maxn],B[maxn],a[maxn];

void DFS(int num,int tot,int use)
{
     if(use==i+1)
     {
        if(tot==Q)
        {
           for(int j=1;j<use;j++)
           Ans[j]=B[j]; 
           flag=1;      
        }         
       return;               
     }    
     B[use]=a[num];
     if(num>N||a[num]>Ans[use])return;
     int m=1;
     while(tot+a[num]*m<=Q)
     {
       DFS(num,tot+a[num]*m,use+1);
       m++;
     }
     if(num<n)DFS(num+1,tot,use);
}

int main()
{
    freopen("milk4.in","r",stdin);
    freopen("milk4.out","w",stdout);
    scanf("%d",&Q);
    scanf("%d",&N);
    for(int x,k=1;k<=N;k++)
    {
         scanf("%d",&x);flag=0;
         for(int j=1;j<=n;j++)
         if(a[j]%x==0)
         {
         a[j]=x;
         break;
         }
         else if(x%a[j]==0)
         {
         flag=1;break;
         }
         if(!flag)a[++n]=x;    
    }
    sort(a+1,a+n+1);
    memset(Ans,60,sizeof(Ans));
    flag=0;
    for(i=1;i<=n;i++)
    {
        DFS(1,0,1);
        if(flag)break;
    }
    printf("%d ",i);
    for(int  j=1;j<=i;j++)
    {
     printf("%d ",Ans[j]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}