题解 P2725 【邮票 Stamps】

xzyxzy

2017-07-04 17:13:22

Solution

首先,有1分的邮票,所以可以从一分开始凑 接下来,用变量i表示当前要凑到的面值,r[i]表示凑到i要用的邮票数量 为使得张数最少,则在凑i时,将i依次减去各个种类的邮票面值m[j],得到的剩余面值a 这样凑i需要的张数r[i],就是凑a需要的张数r[a]+1,然后依次枚举邮票面值相减取得a,取r[a]最小时,再计算r[i],可使得r[i]最小,再重复此过程,直到r[i]=0或者r[i]大于了限定张数为止 最后输出i-1 这样即可保证凑到每个面额中所用的张数是最少的 可以看下我的代码(其实思路明确了完全可以按照自己风格写) ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,k;//n种面值,k张邮票 int m[51];//m存放面值 int r[2000001];//c[i]存放达到总额i需要的最少邮票张数 int read() { char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); int h=0; while(ch<='9'&&ch>='0') { h=h*10+ch-48; ch=getchar(); } return h; } int main() { k=read(); n=read(); for(int i=1;i<=n;i++) m[i]=read(); sort(m+1,m+n+1); r[1]=1; int i=1; while(1) { i++;//要凑到i的面值 int mini=201; for(int w=1;w<=n;w++) { if(i-m[w]>=0) mini=(r[i-m[w]]+1)<mini?(r[i-m[w]]+1):mini; } r[i]=mini; if(mini==0||mini>k) { cout<<i-1; return 0; } } } ```