主题:[讨论]邮票问题的疑问
邮票问题的疑问
问题描述】设有已知面额的邮票m种,每种有n张。问:用总数不超过n张的邮票进行组合,能组合的邮票面额中可以连续出现面额数最多有多少?(1<=m<=100,1<=n<=100,1<=邮票面额<=255)
输入:第一行:n和m的值,中间用一空格隔开。
第二行:a【1..m】(面额),每个数中间用一空格隔开。
输出:连续面额数的最大值
【样例输入】
4 3
1 2 4
【样例输出】
14
这是它的标程:
program p1_2(input,output);
var
a:array [1..100] of integer;
money:array [1..2550] of integer;
total,n,m,i:integer;
procedure search(k,n,x:integer);
var i:integer;
begin
if (n=0)or(k=0) then exit;
for i:=n downto 0 do
begin
x:=x+a[k]*i;
n:=n-i;
money[x]:=money[x]+1;
search(k-1,n,x);
x:=x-a[k]*i;
n:=n+i;
end
end;
function maxlong:integer;
var j,total,max:integer;
begin
j:=n*a[m];
max:=0;
repeat
while (money[j]=0)and(j>0) do
j:=j-1;
total:=0;
while (money[j]>0)and(j>0) do
begin total:=total+1;j:=j-1 end;
if max<total then max:=total ;
until j<=0;
maxlong:=max
end;
begin
assign(input,'word.in');
reset(input);
assign(output,'word.out');
rewrite(output);
readln(m,n);
for i:=1 to m do read(a);
total:=0;
search(m,n,0);
writeln(maxlong)
end.
这里只要money[n]存在即可大于一,那么,会不会造成n超过他应该的最大值呢??(即,如果3-30是一个连续,2-15是一个连续,那么,他们的money都大于0,会不会造成误解为2-30的呢??)如果不会,说明理由。谢谢啦!!
问题描述】设有已知面额的邮票m种,每种有n张。问:用总数不超过n张的邮票进行组合,能组合的邮票面额中可以连续出现面额数最多有多少?(1<=m<=100,1<=n<=100,1<=邮票面额<=255)
输入:第一行:n和m的值,中间用一空格隔开。
第二行:a【1..m】(面额),每个数中间用一空格隔开。
输出:连续面额数的最大值
【样例输入】
4 3
1 2 4
【样例输出】
14
这是它的标程:
program p1_2(input,output);
var
a:array [1..100] of integer;
money:array [1..2550] of integer;
total,n,m,i:integer;
procedure search(k,n,x:integer);
var i:integer;
begin
if (n=0)or(k=0) then exit;
for i:=n downto 0 do
begin
x:=x+a[k]*i;
n:=n-i;
money[x]:=money[x]+1;
search(k-1,n,x);
x:=x-a[k]*i;
n:=n+i;
end
end;
function maxlong:integer;
var j,total,max:integer;
begin
j:=n*a[m];
max:=0;
repeat
while (money[j]=0)and(j>0) do
j:=j-1;
total:=0;
while (money[j]>0)and(j>0) do
begin total:=total+1;j:=j-1 end;
if max<total then max:=total ;
until j<=0;
maxlong:=max
end;
begin
assign(input,'word.in');
reset(input);
assign(output,'word.out');
rewrite(output);
readln(m,n);
for i:=1 to m do read(a);
total:=0;
search(m,n,0);
writeln(maxlong)
end.
这里只要money[n]存在即可大于一,那么,会不会造成n超过他应该的最大值呢??(即,如果3-30是一个连续,2-15是一个连续,那么,他们的money都大于0,会不会造成误解为2-30的呢??)如果不会,说明理由。谢谢啦!!