一道竞赛题
邮票面值设计
给定一个信封，最多只允许粘贴n张邮票，计算在给定k(n|k<=40)种邮票的
情况下（所有的邮票数量足够），如何设计邮票的面值，能得到最大值Max,使
1~Max之间的每一个邮资值都能得到。要求：输入n,k ，输出各面值及Max.
我在女朋友的激励下苦想了一个多小时,还是没思路,好没面子啊!
问题点数：200、回复次数：18Top
1 楼kp（老妖）回复于 2000-10-24 17:12:00 得分 0
关注Top
2 楼ahao（天·狼·星星）回复于 2000-10-24 21:05:00 得分 0
1,2,4,8...?Top
3 楼mutant（异类）回复于 2000-10-27 09:34:00 得分 0
M[1]=1,M[2]=2
l=1~n,
X=(n-l)*M[1]+l*M[2],
如果l连续时X连续,
则M[3]=X(Max)+1,递归得到M[4]...
计算量大,而且好像不是最优解.
Top
4 楼mutant（异类）回复于 2000-10-27 09:50:00 得分 0
M[1]=1,M[2]=2
l=1~n,
X=(n-l)*M[1]+l*M[2],
如果l连续时X连续,
则M[3]=X(Max)+1,递归得到M[4]...
计算量大,而且好像不是最优解.
Top
5 楼mutant（异类）回复于 2000-10-27 10:05:00 得分 0
M[1]=1,M[2]=2
L=1~n
X=(n-L)*M[1]+L*M[2]
如果X连续,则M[3]=X(max)+1
递归得到M[4]...
计算量大,而且不是最优解Top
6 楼lance（我想忘掉所有不眠的夜晚我已厌倦所有..）回复于 2000-10-27 14:35:00 得分 0
你太想当然了！Top
7 楼qiangsheng（做人很厚道）回复于 2000-10-27 14:54:00 得分 0
为什么只有一个回复？明明是11篇嘛！
抱歉问个弱智问题，(n|k<=40)是什么东东？Top
8 楼friendkey（friendkey）回复于 2000-10-27 22:36:00 得分 0
关注Top
9 楼zswang（伴水清清)(专家门诊清洁工）回复于 2000-10-28 13:28:00 得分 0
给大家一个输入/输出范例吧Top
10 楼NowCan（城市浪人）回复于 2000-11-02 18:02:00 得分 0
Let me think and think....Top
11 楼lenyu（剑客。孤星）回复于 2000-11-07 16:50:00 得分 10
广西计算机信息学奥赛97年的初赛和复赛题
算法比较简单，就是回朔穷举，主要的问题就是做一些优化
比如，当时我写的程序，主要做的优化就是第i次的穷举结果根据第i-1次的最大可能来定
然后就是在求最大可能的时候，不是直接一个一个的试看能不能贴到，而是用一个boolean的数组，让各个可能都出现，判断是不是都有true
即使是这样，也只能在贴三张邮票的情况下，出得了k=8的结果（486），9是当时题目的上限，得不到。贴两张邮票的情况下，可以得到k=11的结果。你说的n|k<=40，我看不太可能
Top
12 楼lance2000（）回复于 2000-11-17 17:00:00 得分 190
我要收回分数。Top
