记录编号	81718	评测结果	AAAAAAAAAA
题目名称	量取牛奶	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.306 s
提交时间	2013-11-17 11:44:53	内存使用	0.56 MiB

#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
#include<cstring>
#include<deque>
#include<cstring>
#include<map>
#include<algorithm>
#include<iomanip>
using namespace std;
const int SIZEQ=20001;
const int SIZEP=101;
const int INF=0x3fffffff;
const int W=3;
int f[SIZEQ]={0};
bool flag[SIZEQ]={0};
int Q,P;
int V[SIZEP]={0};
int next1[SIZEQ]={0};
int next2[SIZEQ]={0};
vector<pair<int,int> > gset;
bool better(int x,int y,int k){//x更新成y是否更好
	deque<int> a;
	deque<int> b;
	while(x){
		a.push_back(next2[x]);
		x-=next1[x];
	}
	b.push_back(k);
	while(y){
		b.push_back(next2[y]);
		y-=next1[y];
	}
	int i;
	for(i=0;i<a.size();i++){
		if(a[i]<b[i]) return false;
		if(a[i]>b[i]) return true;
	}
	return false;
}
void init(void){
	int i,j;
	scanf("%d%d",&Q,&P);
	for(i=1;i<=P;i++) scanf("%d",&V[i]);
	sort(V+1,V+1+P);
	for(i=1;i<=P;i++){
		for(j=V[i];j<=Q;j+=V[i]){
			gset.push_back(make_pair(j,V[i]));
		}
	}
}
void output(void){
	deque<int> ans;
	int x=Q;
	cout<<f[Q]<<" ";
	while(x){
		ans.push_back(next2[x]);
		x-=next1[x];
	}
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
	cout<<endl;
}
void DP(void){
	int i,j;
	int v;
	for(i=1;i<=Q;i++) f[i]=INF;
	for(i=gset.size()-1;i>=0;i--){
		v=gset[i].first;
		for(j=Q;j>=v;j--){
			if(f[j]>f[j-v]+1){
				f[j]=f[j-v]+1;
				next1[j]=gset[i].first;
				next2[j]=gset[i].second;
			}
			else{
				if(f[j]==f[j-v]+1&&better(j,j-v,gset[i].second)){
					f[j]=f[j-v]+1;
					next1[j]=gset[i].first;
					next2[j]=gset[i].second;
				}
			}
		}
	}
}
int main(){
	freopen("milk4.in","r",stdin);
	freopen("milk4.out","w",stdout);
	init();
	DP();
	output();
	return 0;
}