查人人中国名人网越南open bus网上购票:邮票面值设计问题（pascal)
来源：百度文库 编辑：查人人中国名人网 时间：2024/04/29 04:06:15
例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为1分、3分。
样例：
INPUT
N=3 K=2
OUTPUT
1 3
MAX=7
program stamp;
const
max_num = 40;
max_total = 50000000;
type
arrtype= array[1..max_num] of integer;
var
n,k,max_max:integer;
value,max_value: arrtype;
num: array[0..max_total] of integer;
count:integer;
last_count:integer;
function get_max(n,k:integer; var value: arrtype): integer;
var
i,j,min_num: integer;
begin
num[0] := 0;
for i := 1 to max_total do
begin
min_num := maxint;
for j := 1 to k do
if ((i-value[j] >= 0) and (num[i-value[j]]+1 < min_num))
then
min_num := num[i-value[j]]+1;
if (min_num > n)
then
begin result := i - 1; exit end;
num[i] := min_num;
end;
result := max_total;
end;
function try_it(index,prev2_max,prev_max: integer): boolean;
var
i,cur_max: integer;
begin
result := false;
if (index = k + 1)
then
begin
inc(count);
if (prev_max > max_max)
then
begin
max_max := prev_max;
max_value := value;
last_count := count;
end;
exit;
end;
for i := prev_max + 1 downto value[index-1] + 1
do
begin
if ((index = k) and (i*n <= max_max))
then
break;
value[index] := i;
cur_max := get_max(n,index,value);
if (try_it(index+1,prev_max,cur_max))
then
begin result := true; exit; end;
end;
end;
var
i: integer;
begin
write('input n k: ');
readln(n,k);
if ((n < 1) or (n > max_num) or (k < 1) or (k > max_num))
then
exit;
value[1] := 1;
max_max := -1;
count := 0;
last_count := 0;
try_it(2, 0, n);
for i := 1 to k
do
write(max_value[i],' ');
writeln;
writeln('MAX=',max_max);
readln;
end.
program stamp;
const
max_num = 40;
max_total = 50000000;
type
arrtype= array[1..max_num] of integer;
var
n,k,max_max:integer;
value,max_value: arrtype;
num: array[0..max_total] of integer;
count:integer;
last_count:integer;
function get_max(n,k:integer; var value: arrtype): integer;
var
i,j,min_num: integer;
begin
num[0] := 0;
for i := 1 to max_total do
begin
min_num := maxint;
for j := 1 to k do
if ((i-value[j] >= 0) and (num[i-value[j]]+1 < min_num))
then
min_num := num[i-value[j]]+1;
if (min_num > n)
then
begin result := i - 1; exit end;
num[i] := min_num;
end;
result := max_total;
end;
function try_it(index,prev2_max,prev_max: integer): boolean;
var
i,cur_max: integer;
begin
result := false;
if (index = k + 1)
then
begin
inc(count);
if (prev_max > max_max)
then
begin
max_max := prev_max;
max_value := value;
last_count := count;
end;
exit;
end;
for i := prev_max + 1 downto value[index-1] + 1
do
begin
if ((index = k) and (i*n <= max_max))
then
break;
value[index] := i;
cur_max := get_max(n,index,value);
if (try_it(index+1,prev_max,cur_max))
then
begin result := true; exit; end;
end;
end;
var
i: integer;
begin
write('input n k: ');
readln(n,k);
if ((n < 1) or (n > max_num) or (k < 1) or (k > max_num))
then
exit;
value[1] := 1;
max_max := -1;
count := 0;
last_count := 0;
try_it(2, 0, n);
for i := 1 to k
do
write(max_value[i],' ');
writeln;
writeln('MAX=',max_max);
readln;
end.
递归解决