1. (过河问题) 在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2<=N<1000)和这N个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸.
例如,有3个人甲、乙、丙,他们单独过桥的时间分别为1 2 4,则总共最少需要的时间为7.具体方法是:甲 乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲,丙在一起过桥到河的左岸,总时间为2+1+4=7.
const
SIZE = 100;
INFINITY = 10000;
LEFT = true;
RIGHT = false;
LEFT_TO_RIGHT = true;
RIGHT_TO_LEFT = false;
var
n, i : integer;
time : array[1..Size] of integer;
pos :array[1..Size] of Boolean;
function max(a, b :integer) : integer;
begin
if a > b then
max := a
else
max := b;
end;
function go(stage : boolean) : integer;
var
i, j, num, tmp, ans : integer;
begin
if (stage = RIGHT_TO_LEFT)
then begin
num := 0;
ans :=0;
for i := 1 to n do
if pos[i] = Rignt then
begin
inc(num);
if time[i] > ans then
ans := time[i];
end;
if num<=2 then
begin
go := ans;
exit;
end;
ans := INFINITY;
for i := 1 to n – 1 do
if pos[i] = RIGHT then
for j := i+1 to n do
if pos[j] = RIGHT then
begin
pos[i] := LEFT;
pos[j] := LEFT;
tmp := max(time[i], time[j]) + go(LEFT_TO_RIGHT) ;
if tmp < ans then
ans := tmp;
pos[i] := RIGHT;
pos[j] := RIGHT;
end;
go := ans;
end
else if (stage = LEFT_TO_RIGHT)
then begin
ans := INFINITY;
for i := 1 to n do
if pos[i]=LEFT then
begin
pos[i] := RIGHT;
tmp := time[i]+go(RIGHT_TO_LEFT) ;
if tmp < ans then
ans := tmp;
pos[i]:=LEFT ;
end;
go := ans;
end
else go := 0;
end;
begin
readln(n);
for i := 1 to n do
begin
read(time[i]);
pos[i] := RIGHT;
end;
writeln(go(RIGHT_TO_LEFT));
end.
2. （烽火传递）烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情。在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传递，在连续的m个烽火台中至少要有一个发出信号。现输入n、m和每个烽火台发出信号的代价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传递。 例如，有5个烽火台，他们发出信号的代价依次为1，2，5，6，2，，且m为3，则总共最少花费代价为4，即由第2个和第5个烽火台发出信号。
const
SIZE = 100;
var
n, m, r, i : integer;
value, heap, pos, home, opt : array[1..SIZE] of integer;
//heap[i]表示用顺序数组存储的堆 heap 中第 i个元素的值
//pos[i]表示opt[i]在堆heap中的位置，即 heap[pos[i]]=opt[i]
//home[i]表示heap[i]在序列opt中的位置，即 opt[home[i]]=heap[i]
procedure swap(i, j : integer);
//交换堆中的第i 个和第j 个元素
var
tmp : integer;
begin
pos[home[i]] := j;
pos[home[j]] := i;
tmp := heap[i];
heap[i] := heap[j];
heap[j] := tmp;
tmp := home[i];
home[i] := home[j];
home[j] := tmp;
end;
procedure add(k : integer);
//在堆中插入opt[k]
var
i : integer;
begin
inc(r);
heap[r] := opt[k] ;
pos[k] := r;
home[r]:=k ;
i := r;
while (i > 1) and (heap[i] < heap[i div 2]) do
begin
swap(i, i div 2);
i := i div 2;
end;
end;
procedure remove(k : integer);
//在堆中删除opt[k]
var
i, j : integer;
begin
i := pos[k];
swap(i, r);
dec(r);
if i = r + 1 then
exit;
while (i > 1) and (heap[i] < heap[i div 2]) do
begin
swap(i, i div 2);
i := i div 2;
end;
while i + i <= r do
begin
if (i + i + 1 <= r) and (heap[i + i + 1] < heap[i + i]) then
j := i + i + 1
else
j:=2*i ;
if heap[i] > heap[j] then
begin
swap(i,j) ;
i := j;
end
else
break;
end;
end;
begin
readln(n, m);
for i := 1 to n do
read(value[i]);
r := 0;
for i := 1 to m do
begin
opt[i] := value[i];
add(i);
end;
for i := m + 1 to n do
begin
opt[i] := value[i]+heap[1] ;
remove( i-m );
add(i);
end;
writeln(heap[1]);
end.