邮票问题-阿里云开发者社区

开发者社区> 华山青竹> 正文

邮票问题

简介: 题目链接: http://www.joyoi.cn/problem/tyvj-1199 http://tyvj.cn/p/1199 题目限制 时间限制 内存限制 评测方式 题目来源 1000ms 131072KiB 标准比较器 Local 题目描述 给定一个信封,最多只允许粘贴N(N≤100)张邮票,我们现在有M(M≤100)种邮票,面值分别为:X1,X2……Xm(Xi≤255为正整数),并假设各种邮票都有足够多张。
+关注继续查看

题目链接:

http://www.joyoi.cn/problem/tyvj-1199

http://tyvj.cn/p/1199

题目限制

时间限制 内存限制 评测方式 题目来源
1000ms 131072KiB 标准比较器 Local

题目描述

给定一个信封,最多只允许粘贴N(N≤100)张邮票,我们现在有M(M≤100)种邮票,面值分别为:X1,X2……Xm(Xi≤255为正整数),并假设各种邮票都有足够多张。
要求计算所能获得的邮资最大范围。即求最大值MAX,使1-MAX之间的每一个邮资都能得到。
例如:N=4,有2种邮票,面值分别为1分,4分,于是可以得到1-10分和12分,13分,16分邮资,由于得不到11分和15分,所以邮资的最大范围max=10

输入格式

第一行为最多粘贴的邮票张数n。第二行为邮票种数m。以下m行各有一个数字表示邮票的面值。

本地测试的输入格式:

第一行:m,n的值,中间用一空格隔开。

第二行:A[1..m](面额),每个数中间用一空格隔开。

输出格式

仅一个数,最大的max的值。

算法分析:

从面额1开始,建立递推关系方程。比如:面额1,2,4只用1张邮票行了,面额3可以表示为面额1,2的邮票和1+1=2张邮票,面额5有两种表示方式min(面额1+面额4,面额2+面额3)邮票数目……照此类推,递推关系方程不难建立,以下是递推的一种方法: 

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 int main()
 5 {
 6     freopen("stamp_data/STAMP14.in","r",stdin);
 7     freopen("stamp_data/STAMP14.txt","w",stdout);
 8     int n,m,i,j,c[256]={0},a[31001]={0};
 9     int b1=1;
10 
11     scanf("%d%d",&m,&n);//local test
12     //scanf("%d%d",&n,&m);//online judge
13     for(i=1;i<=m;i++)
14     {
15         scanf("%d",&c[i]);
16         if(c[i]==1) b1=0;
17     }
18 
19     if(b1==1) printf("0\n");
20     else
21     {
22         i=1; a[1]=1;//a[i]=x表示构造i这个值用x张邮票
23         do
24         {
25             i++;
26             for(j=1;j<=m;j++)
27             {
28                 if( (i%c[j]==0)&&( (i/c[j]<a[i]) || (a[i]==0) ))
29                     a[i]=i/c[j];  //判断它能否被题目给定面额整除
30             }
31             for(j=1;j<=i/2;j++)   //寻找 1<= j <=i使得a[j]+a[i-j]值最小
32                 if(a[j]+a[i-j]<a[i]) a[i]=a[j]+a[i-j];
33         }while((a[i]<=n)&&(a[i]!=0));
34         printf("%d\n",i-1);
35     }
36     return 0;
37 }

这种递推方法原理是:对于某种要求得到的面额,判断它能否被题目给定面额整除,再寻找(1<=j<=i),使A[j]+A[i-j]值最小,求出凑成某种面额最少邮票数。

 

这种递推方法虽然简单,由于1<=邮票面额<=255,1<=n<=100,因此MAX值最多可达到25500,25500次循环里必定还有嵌套循环,因此算法不加优化,很难在规定时间内得出最优值。这就需要递推的算法优化。

进一步优化

何不将用m种面额邮票作循环,建立递推关系式:A[i]=min(A[i-C[j]]+1),于是当取到极限值时,程序减少了约1.6*10^8次循环,递推优化作用不言而喻。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 int main()
 5 {
 6     freopen("stamp_data/STAMP0.in","r",stdin);
 7     freopen("stamp_data/STAMP0.txt","w",stdout);
 8     int x[256]={0},pieces[30001]={0};
 9     int n,m,i;
10     int maxX=0;
11     scanf("%d%d",&m,&n);  //local test
12     //scanf("%d%d",&n,&m);  //online judge
13     for(i=1;i<=m;i++)
14         scanf("%d",&x[i]);
15     do
16     {
17         maxX++;
18         for(i=1;i<=m;i++)
19         {
20             if(maxX-x[i]>=0)
21             {
22                 if(pieces[maxX]==0) pieces[maxX]=pieces[maxX-x[i]]+1;
23                 if(pieces[maxX]>pieces[maxX-x[i]]+1) pieces[maxX]=pieces[maxX-x[i]]+1;
24             }
25         }
26         if(pieces[maxX]==0 || pieces[maxX]>n)
27         {
28             printf("%d\n",maxX-1);
29             break;
30         }
31     }while(1);
32     return 0;
33 }

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9950 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13699 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
9130 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
7450 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
4437 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
22336 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7312 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载