题目描述
给一组N枚邮票的面值集合（如，{1分，3分}）和一个上限K——表示信封上能够贴K张邮票。计算从1到M的最大连续可贴出的邮资。
例如，假设有1分和3分的邮票；你最多可以贴5张邮票。很容易贴出1到5分的邮资（用1分邮票贴就行了），接下来的邮资也不难：
然而，使用5枚1分或者3分的邮票根本不可能贴出14分的邮资。因此，对于这两种邮票的集合和上限K=5，答案是M=13。
（规模最大的一个点的时限是3s）
小提示：因为14贴不出来，所以最高上限是13而不是15。
输入输出格式
输入格式：
第1行，两个整数，K和N。K（1≤K≤200）是可用的邮票总数。N（1≤N≤50）是邮票面值的数量。
第2行至末尾：N个整数，每行15个，列出所有的N个邮票的面值，每张邮票的面值不超过10000。
输出格式：
一行，一个整数，从1分开始连续的可用集合中不多于K张邮票贴出的邮资数。
输入输出样例
输入样例：
5 2
1 3
输出样例：
13
这道题是一道简(jv)单(nan)的DP题
dp[i]表示面值为i的邮资至少用dp[i]张邮票表示
因为dp[i]的值就是i-a[j]元邮资加a[j]这张邮票
所以得到动态转移方程：
dp[i]=min(dp[i],dp[i-a[j]]+1);
代码：
#include<iostream>
using namespace std;
long long k,n,a[55],ans,dp[10000005];
int main()
{
cin>>k>>n;
for(register int i=1;i<=n;++i) cin>>a[i];
for(register int i=1;;++i)
{
dp[i]=2147483647;
for(register int j=1;j<=n;++j) if(i-a[j]>=0) dp[i]=min(dp[i],dp[i-a[j]]+1);
if(dp[i]>k)
{
ans=i-1;
break;
}
}
cout<<ans;
}