记录编号	52029	评测结果	AAAAAAAAAAAAA
题目名称	邮票	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.679 s
提交时间	2013-01-09 21:23:03	内存使用	4.81 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
	freopen("stamps.in","r",stdin);
	freopen("stamps.out","w",stdout);
	int s[50]={0},f[2000001]={0};
	int n,k;//邮票面值数和可用邮票数
	scanf("%d%d",&k,&n);
	int i,j;
	for(i=0;i<n;i++) scanf("%d",&s[i]);
	sort(s,s+n);
	int temp;
	//此前f[0]=0
	for(i=1;i<=2000000;i++){
		f[i]=998;//只要998!只要998!(反正k<=200)
		for(j=0;j<n;j++){
			if(s[j]>i) break;
			temp=f[i-s[j]]+1;
			if(temp<f[i]) f[i]=temp;
		}
		if(f[i]>k) break;
	}
	printf("%d\n",i-1);
	return 0;
}