记录编号	317072	评测结果	AAAAAAAAAA
题目名称	量取牛奶	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.114 s
提交时间	2016-10-07 17:08:36	内存使用	0.62 MiB

// 完全背包

#include "cstdio"
#include "cstring"
#include "iostream"
#include "algorithm"
#include "vector"
using namespace std;

int Q, P, c[110];
int f[20100];
// f[i]: 量i体积的牛奶使用桶的最小数量
vector <int> v[20100];

#define SUBMIT
int main()
{
#ifdef SUBMIT
	freopen("milk4.in", "r", stdin); freopen("milk4.out", "w", stdout);
#endif	

	scanf("%d%d", &Q, &P);
	for(int i = 1; i <= P; i++){
		scanf("%d", &c[i]);
		if(c[i] == 1 || Q / c[i] == 0){
			printf("1 %d\n", i);
			goto END;
		}
	}
	sort(c+1, c+1+P);

	memset(f, 0x3f, sizeof(f));
	f[0] = 0; 
	for(int j = 0; j <= Q; j++){
		for(int i = 1; i <= P && c[i] <= j; i++){
			for(int k = 1; k * c[i] <= j; k++){
				if(f[j] > f[j - k * c[i]] + 1){
					f[j] = f[j - k * c[i]] + 1;
					v[j].clear();
					for(int p = 0; p < (int)v[j - k * c[i]].size(); p++)
						v[j].push_back(v[j - k * c[i]][p]);
					v[j].push_back(c[i]);
				}
				else if(f[j] == f[j - k * c[i]] + 1){
					for(int p = 0; p < (int)v[j - k * c[i]].size(); p++){
						if(v[j][p] > v[j - k * c[i]][p]){
							v[j].clear();
							for(int p = 0; p < (int)v[j - k * c[i]].size(); p++)
								v[j].push_back(v[j - k * c[i]][p]);
							v[j].push_back(c[i]);
							break;		
						}
					}
				}
			}
		}
	}

	printf("%d ", f[Q]);
	for(int i = 0; i < (int)v[Q].size(); i++) printf("%d ", v[Q][i]);
	END:

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else 
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}