首页 > 代码库 > [usaco3.1]邮票 Stamps
[usaco3.1]邮票 Stamps
题目链接
思路分析：
dp[n]表示组成数字n最少需要多少张邮票
每读入一个x，我们就可以从x向2000000（最极限情况，即200张邮票和10000的面值）更新。
首先dp[n-x]必须<m 并且大于0，其次dp[n]必须>dp[n-x]+1（dp[n]=0除外）,这样每次更新一次 dp[n]=dp[n-x]+1
最后从1遍历到2000000 如果中间出现断点就记录断点前一个数的值就可以了。
1 #include <cstdio> 2 int dp[2000005],m,n,ans; 3 int main(){ 4 scanf("%d%d",&m,&n); 5 for(register int i=1;i<=n;i++){ 6 int x; //register 是在寄存器里面运算 是为了加快速度 7 scanf("%d",&x); 8 dp[x] = 1; 9 for(register int j=x+1;j<=2000000;j++){10 if(dp[j-x] && dp[j-x]<m && (!dp[j] ||dp[j]>dp[j-x]+1)) dp[j] = dp[j-x]+1;11 }12 }13 for(register int i=1;i<=2000000;i++){14 if(dp[i]) ans=i;15 else break;16 }17 printf("%d",ans);18 return 0;19 }
[usaco3.1]邮票 Stamps
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。