题解 P2725 【邮票 Stamps】
xzyxzy
2017-07-04 17:13:22
首先,有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;
}
}
}
```