题目
思路
( exttt{dp})。( exttt{dp[i]})表示拼出邮资(i)最少需要几张邮票。
状态转移方程：( exttt{dp[i]=min(dp[i],dp[i-value]+1)})
(Code)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[51],f[2000001];
inline void read(int &T){
int x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
int main(){
read(n),read(m);
int maxx=0;
memset(f,0x3f3f3f,sizeof(f));
for(int i=1;i<=m;++i){
read(a[i]);
maxx=max(a[i],maxx);
}
int stop=maxx*n;
f[0]=0;
for(int j=1;j<=m;++j){
for(int i=1;i<=stop;++i){
if(a[j]>i) continue;
f[i]=min(f[i],f[i-a[j]]+1);
}
}
for(int i=1;i<=stop;++i){
if(f[i]>n){
printf("%d
",i-1);
return 0;
}
}
printf("%d
",stop);
return 0;
}