题解 GDFZOJ 【649】 邮票问题

看原题戳[这儿](http://u.gdfzoj.com/problem/649) # 一、审题 给定一个信封，最多只允许粘贴$n(n\le100)$张邮票，我们现在有$m(m\le100)$种邮票，面值分别为：$x_1,x_2,······,x_m(xi\le255,\text{为正整数})$分，并假设各种邮票都有足够多张。要求计算所能获得的邮资最大范围。即求最大值$MAX$，使在$1-MAX$之间的每一个邮资值都能得到。 很明显，这是一道$Dp$的题目 # 二、做题 众所周知，$Dp$的题目主要就是要推式子，所以就开始推式子吧 我们先定义一个状态$f_j$表示要凑到面值为j分的邮票最少需要多少张邮票，容易得到，若果我们有一张面值为$x$的邮票，那么$f_j=f_{j-x}+1$，不过有可能这并不是最优的解法呀，所以我们需要取一个$max$，于是我们的式子就这么简单地推出来了: $$ f_j=max(f_j,f_{j-x}+1) $$ # 三、代码 ```cpp #include<bits/stdc++.h> using namespace std; int a,b,i,j,ans; int f[2000000]; int main() { scanf("%d%d",&a,&b); for(i=1;i<=2000000;i++) f[i]=1e9; f[0]=0; for (i=1;i<=b;i++) { int x; scanf("%d",&x); for(j=x;j<=2000000;j++) if(f[j-x]+1<=a) f[j]=min(f[j],f[j-x]+1); } ans=0; for(i=1;i<=2000000;i++) if(f[i]==1e9) { ans=i-1; break; } printf("MAX=%d\n",ans); return 0; } ```