QhdongDOC

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (373.29 KB, 91 trang )

(1)<div class='page_container' data-page=1>

I.

Quy hoạch động

1. Phơng pháp quy hoạch động

2. Các bớc thực hiện

3. Hạn chế của quy hoch ng

4. Mt vi vớ d

II.

Một số bài toán tiêu biểu

(Phát biểu, phân tích thuật toán và tổ chức dữ liệu, chơng trình)

III.

Các bài tập luyện tập

1. Đề bµi

2. Híng dÉn

IV.

Các đề tự giải

I. quy họach động

1. Phơng pháp quy hoạch động

</div>
(2)<div class='page_container' data-page=2>

Trong thực tế, ta thờng gặp một số bài toán tối u loại sau: Có một đại lợng f
hình thành trong một quá trình gồm nhiều giai đoạn và ta chỉ quan tâm đến kết quả
cuối cùng là trị của f phải lớn nhất hoặc nhỏ nhất, ta gọi chung là giá trị tối u của f.
Giá trị của f phụ thuộc vào những đại lợng xuất hiện trong bài toán mà mỗi bộ giá
trị của chúng đợc gọi là một trạng thái của hệ thống và cũng phụ thuộc vào cách
thức đạt đợc giá trị f trong từng giai đoạn mà mỗi cách thức đợc gọi là một điều
khiển. Đại lợng f thờng đợc gọi là hàm mục tiêu và quá trình đạt đợc giá trị tối u
của f đợc gọi là quá trình điều khiển tối u.

Bellman phát biểu nguyên lý tối u (cũng còn gọi là nguyên lý Bellman) nh sau:
" Với mỗi quá trình điều khiển tối u, đối với trạng thái bắt đầu A0, nếu giữa chừng
ta đi đến một trạng thái A nào đó thì phần q trình đó kể từ trạng thái A xem nh
trạng thái bắt đầu cũng là tối u."

Chú ý rằng nguyên lý này đợc thừa nhận và khơng chứng minh.

Phơng pháp tìm điều khiển tối u theo nguyên lý Bellman thờng đợc gọi là quy
hoạch động. Thuật ngữ này nói lên đợc thực chất của q trình điều khiển là động:
có thể trong một số bớc đầu tiên lựa chọn điều khiển tối u dờng nh không tốt nhng
tựu chung cả quá trình lại là tốt nhất.

Ta có thể giải thích ý này qua bài toán sau:

Cho một dãy N số nguyên A1, A2, ..., AN. Hãy tìm cách xố đi một số ít nhất số
hạng để dãy còn lại là đơn điệu hay tơng đơng hãy chọn một số nhiều nhất các số
hạng sao cho dãy B gồm các số hạng đó theo trình tự xuất hiện trong dãy A là đơn
điệu.

Quá trình chọn dãy B đợc điều khiển qua N giai đoạn để đạt đợc mục tiêu là số
lợng số hạng của dãy B là nhiều nhất, điều khiển ở giai đoạn i thể hiện việc chọn
hay không chọn Ai vào dãy B.

Giả sử dãy đã cho là 1 8 10 2 4 6 7. Nếu ta chọn lần lợt 1, 8, 10 thì chỉ chọn
đợc 3 số hạng nhng nếu bỏ qua 8 và 10 thì ta chọn đợc 5 số hạng 1, 2, 4, 6, 7 .

Khi giải một số bài toán bằng cách “chia để trị” , chuyển việc giải bài tốn kích
thớc lớn về việc giải nhiều bài tốn cùng kiểu có kích thớc nhỏ hơn. Các thuật toán
này thờng đợc thể hiện bằng các chơng trình con đệ quy. Khi đó, trên thực tế,

nhiều kết quả trung gian phải tính nhiều lần.

</div>
(3)<div class='page_container' data-page=3>

chính là kết quả của bài tốn cần giải. Nói cách khác phơng pháp quy hoạch động
đã thể hiện sức mạnh của nguyên lý chia để trị đến mức cực độ.

Quy hoạch động là kỹ thuật thiết kế bottom-up (từ dới lên). Nó đợc bắt đầu với
những trờng hợp con nhỏ nhất (thờng là đơn giản nhất và giải đợc ngay). Bằng
cách tổ hợp các kết quả đã có (khơng phải tính lại) của các trờng hợp con, sẽ đạt
tới kết quả của trờng hợp có kích thớc lớn dần lên và tổng quát hơn, cho đến khi
cuối cùng đạt tới lời giải của trờng hợp tổng quát nhất.

Trong một số trờng hợp, khi giải một bài tốn A, trớc hết ta tìm họ bài tốn
A(p) phụ thuộc tham số p (có thể p là một véc tơ) mà A(p0)=A với p0 là trạng thái
ban đầu của bài tốn A. Sau đó tìm cách giải họ bài toán A(p) với tham số p bằng
cách áp dụng nguyên lý tối u của Bellman. Cuối cùng cho p=p0 sẽ nhận đợc kết
quả của bài toán A ban đầu.

2. Các bớc thực hiện quy hoạch động

Bíc 1: LËp hÖ thøc

 Dựa vào nguyên lý tối u tìm cách chia q trình giải bài tốn thành từng giai
đoạn sau đó tìm hệ thức biểu diễn tơng quan quyết định của bớc đang xử lý với
các bớc đã xử lý trớc đó. Hoặc tìm cách phân rã bài tốn thành các "bài tốn
con" tơng tự có kích thớc nhỏ hơn, tìm hệ thức nêu quan hệ giữa kết quả bài
tốn kích thớc đã cho với các kết quả của các "bài tốn con" cùng kiểu có kích
thớc nhỏ hơn của nó nhằm xây dựng phơng trình truy tốn (dạng hàm hoặc
thủ tục đệ quy)

.Về một cách xây dựng phơng trình truy toán:

Ta chia việc giải bài toán thành N giai đoạn. Mỗi giai đoạn i có trạng thái
ban đầu của nó là t(i) và chịu tác động điều khiển d(i) sẽ biến thành trạng thái
tiếp theo t(i+1) của giai đoạn i+1 (i=1,2,..,n-1). Theo nguyên lý tối u của
Bellman thì việc tối u giai đoạn cuối cùng khơng làm ảnh hởng đến kết quả
tồn bài tốn. Với trạng thái ban đầu là t(N) sau khi làm giai đoạn N tốt nhất ta
có trạng thái ban đầu của giai đoạn N-1 là t(N-1) và tác động điều khiển của
giai đoạn N-1 là d(N-1), có thể tiếp tục xét đến giai đoạn N-1. Sau khi tối u giai
đoạn N-1 ta lại có t(N-2) và d(N-2) và lại có thể tiến hành tối u giai đoạn N-2 ...
cho đến khi các giai đoạn từ N giảm đến 1 đợc tối u thì coi nh hồn thành bài
tốn. Gọi giá trị tối u của bài tốn tính đến giai đoạn k là Fk, giá trị tối u của bài
tốn tính riêng ở giai đoạn k là Gk thì

</div>
(4)<div class='page_container' data-page=4>

Fk(t(k)) = Max { Gk(t(k), d(k)) + Fk-1 (t(k-1))} (*)
d(k)

Bớc 2: Tổ chức dữ liệu và chơng trình
Tổ chức dữ liệu sao cho đạt các yêu cầu sau:
a- Dữ liệu đợc tính tốn dần theo từng bớc

b- Dữ liệu đợc lu trữ để giảm lợng tính tốn lặp lại.

c- Kích thớc miền nhớ dành cho lu trữ dữ liệu càng nhỏ càng tốt, kiểu dữ liệu đợc
chọn phù hợp, nên chọn đơn giản dễ truy cập.

Cơ thĨ:

 Các giá trị của Fk thờng đợc lu trữ trong một bảng (mảng một chiều hoặc hai,
ba v.v.. chiều).

 Cần lu ý khởi trị các giá trị ban đầu của bảng cho thích hợp, đó là các kết quả
của các bài tốn con có kích cỡ nhỏ nhất của bài toán đang giải.

F1(t(1)) = Max { G1(t(1),d(1)) + F0 (t(0))}
D(1)

 Dựa vào công thức, phơng trình truy tốn (*) và các giá trị đã có trong bảng để
tìm dần các giá trị cịn lại của bng.

Ngoài ra còn cần mảng lu trữ nghiệm tơng ứng với giá trị tối u trong từng giai
đoạn

Da vào bảng lu trữ nghiệm và bảng giá trị tối u từng giai đoạn đã xây dựng,
tìm ra kết qu bi toỏn.

Bớc 3: Làm tốt

Làm tốt thuật toán bằng cách thu gọn hệ thức (*) và giảm kích thớc miền
nhớ. Thờng tìm cách dùng mảng 2 một chiều thay cho mảng hai chiều nếu giá trị
một dòng (hoặc cột) của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cét) kỊ
tr-íc.

Trong mét sè trêng hỵp cã thĨ thay mảng 2 chiều với các giá trị phần tử chỉ
nhận giá trị 0, 1 bởi mảng 2 chiều mới bằng cách dùng kỹ thuật quản lý bít.

3. Hn ch ca quy hoạch động

</div>
(5)<div class='page_container' data-page=5>

 Khi bảng lu trữ địi hỏi mảng hai, ba chiều.. thì khó có thể xử lý dữ liệu với
kích cỡ mỗi chiều lớn hàng trăm.

 Có những bài tốn khơng thể giải dợc bằng quy hoạch động.

4. Mét vµi vÝ dơ

VÝ dơ 1: TÝnh tỉ hỵp chËp k cđa n.
¿

Cn −1k −1+Cn−1k . .. . .. .. 0<k<n
1. . .. .. .. . .. .. . .. .. . .. .k=0, n

¿Cnk={
¿

Chóng ta có ngay công thức truy hồi quen thuộc

là:

Nếu chúng ta tÝnh tỉ hỵp chËp k cđa n trùc tiÕp b»ng hµm:

Function C(n,k)

If (k=0) or (k=n) then C:= 1
Else C:= C(n-1,k-1)+C(n-1,k).

thì nhiều lần sẽ phải tính đi tính lại giá trị C(i,j) (i<n) (j<k). Do đó thời gian thực
hiện của thuật toán này lớn theo sự lặp lại. Chúng ta cũng gặp hiện tợng tơng tự
khi tính dãy số Fibonacci.

Ngợc lại nếu sử dụng bảng chứa các kết quả trung gian (bảng có dạng tam giác
Pascal) chúng ta sẽ đạt đợc một thuật toán hiệu suất hơn. Bảng sẽ đợc làm đầy dần

theo từng dòng.

0 1 2 3 .. k-1 k

0 1

1 1 1

2 1 2 1

n-1 .. .. .. .. C(n-1,k-1) C(n-1,k)

n C(n,k)

Cũng có thể chỉ cần dùng một véc tơ dài là k, véc tơ này biểu diễn cho dòng
hiện thời (dịng thứ n+1) của tam giác Pascal tính đến cột k+1 và chúng ta sẽ cập
nhật các giá trị vào nó từ trái qua phải. Do vậy thuật tốn đợc thực hiện trong thời
gian O(n.k) và chiếm không gian O(k) nếu coi phép cộng là phép toán cơ bản:

Ch

</div>
(6)<div class='page_container' data-page=6>

const max = 20;

var n i,j,k : byte;

C : array[0..max] of longint;

p1,p2 : longint;

BEGIN

clrscr;

write('n, k ='); readln(n,k);
C[0] := 1;{C(0,1)=1}

C[1] := 1;{C(1,1)=1}
for i:=2 to n do
begin

p1 := 1;

for j:=1 to i-1 do
begin

p2 := C[j];
C[j] := p1 + p2;
p1 := p2;
end;

C[i] := 1;
end;

write(f,C[k],' ');
close(f);

END.

Ví dụ 2: Tính số Catalan Phát biểu bài tốn: Xét tích các số Mi (i=1,2,..,n)
là: M=M1.M2.. Mn. Hỏi có bao nhiêu cách chèn cặp dấu ngoặc đơn vào tích này để
đợc các cách biểu diễn khác nhau của tích này?

Cụ thể: Tích ABCD có 5 cách đặt ngoặc khác nhau:

</div>
(7)<div class='page_container' data-page=7>

Phân tích bài tốn: Gọi số cách đặt ngoặc trong trờng hợp có n thừa số là T(n).
Bài tốn trở thành tìm cách tính T(n) khi biết n. Bài tốn này cha cho trc tip cụng
thc truy toỏn.

Ta cần phải xây dựng công thức truy toán tính T(n).

Nhn thy trong cỏc cách đặt ngoặc luôn tồn tại một cách đặt dấu ngoc chia
T(n)=

i=1
n 1

T(i).T(n i)(1) tích thành hai phần: phần trái có i thừa số, phần phải

cú n-i tha s, với i = 1, 2, ..., n-1. Có T(i) cách đặt ngoặc cho phần bên trái và
T(n-i) cách đặt ngoặc cho phần bên phải nên có cơng thức:

Ngồi ra với điều kiện ban đầu T(1)=1, chúng ta có thể tính đợc giá trị của T
nh trong bảng sau:

N 1 2 3 4 5 10 15

T(n) 1 1 2 5 14 4862 2674440

Các giá trị của T(n) đợc gọi là các số Catalan.

Dựa vào công thức truy hồi (1) chúng ta tính T(n) bằng quy hoạch động. Giá trị
các phần tử của mảng T đợc xây dựng dần từ 1 đến n:

T(i)=

∑

j=1
i −1

T(j).T(i − j)¿(∀i=2,. ., n) T[1] = 1;

Ch

ơng trình :
{$E+,N+}
uses crt;

var t : array[1..100] of extended;
n : integer;

procedure tinh;

var i,j : integer;
begin

fillchar(t,sizeof(t),0);
t[1] := 1;

for i:=2 to n do

for j:=1 to i-1 do

t[i] := t[i]+t[j]*t[i-j];
end;

BEGIN

</div>
(8)<div class='page_container' data-page=8>

tinh;

writeln(t[n]:0:0);
END.

Ví dụ 3: Tìm đờng đi ngắn nhất giữa các cặp hai đỉnh trên đồ thị n đỉnh,
có trọng số, khơng có chu trình âm (thuật toán Floyld).

Xây dựng mảng hai chiều A[1.. N,1.. N] với ý nghĩa giá trị cuối cùng tính
đ-ợc của A[i,j] là độ dài đờng đi ngắn nhất từ đỉnh i tới đỉnh j. Đồng thời dùng mảng
G[1.. N,1.. N] với ý nghĩa G[i,j]=k nếu k là đỉnh trung gian mà đờng đi ngắn nhất
từ i tới j phải qua k, đó là đỉnh thoả mãn: A[i,k]+A[k,j]<A[i,j].

Nh vậy mỗi khi tìm đợc đỉnh k, bài tốn đã đợc phân rã thành hai bài tốn
t-ơng tự là tìm đờng đi ngắn nhất từ i đến k và tìm đờng đi ngắn nhất từ k đến j.

Ví dụ 4: Tìm đờng đi ngắn nhất từ đỉnh x đến đỉnh y trên đồ thị n đỉnh, có
trọng số khơng âm (thuật tốn Dijkstra).

áp dụng nguyên lý quy hoạch động của Bellman bằng kỹ thuật gán nhãn
(xem chơng Đồ thị hữu hạn và cỏc thut toỏn c bn).

II. Một số bài toán tiêu biểu:
Bài 1:(DÃy con không giảm dài nhất)

Ai1, Ai2, Ai3,. . ., Aik() Cho N số nguyên dơng (0<N10

4) và một dãy A1,
A2,..., An các số nguyên. Tìm trong dãy đã cho một dãy con

tho¶ m·n các điều kiện:
Aij Aij

+1 a)
b) ij < i j+1
c) k lớn nhất

Dữ liệu vào: File BL1.INP có cấu trúc nh sau:

+ Dòng thứ nhất ghi số N

+ Các dòng tiếp theo chứa dÃy A1, A2,..., An mỗi dòng 10 số (trừ dòng cuối cùng
có thể ít hơn 10 số), các số cách nhau ít nhất một dấu cách.

Dữ liƯu ra : File BL1.OUT cã cÊu tróc nh sau:

+ Dßng thø nhÊt ghi sè k

</div>
(9)<div class='page_container' data-page=9>

Híng dÉn: Xây dựng mảng T và mảng D với ý nghÜa:

T[i]=j là chỉ số j (trong dãy (*)) của phần tử đứng ngay trớc Ai trong dãy kết
quả. Cách tính T[i]: duyệt mảng A từ vị trí 1 đến vị trí i-1, tìm vị trí j có D[j] lớn

nhất trong số các vị trí j thoả mãn A[j]A[i].

D[i] là độ dài của dãy kết quả khi bài tốn chỉ xét dãy A1, A2,..., Ai và đợc tính
theo công thức truy hồi:

D[i] = Max { D[j] +1  j mµ j<i vµ AjAi }
Chó ý khëi trÞ: T[1]:= 0 ; D[1]:= 1; VÝ dô:

I 1 2 3 4 5 6 7 8 9 10 11 12

A[i] 6 12 8 11 3 4 1 7 5 9 10 2

T[i] 0 1 1 3 0 5 0 6 6 8 10 7

D[i] 1 2 2 3 1 2 1 3 3 4 5 2

Khi duyệt ngợc tìm kết quả ta tiến hành nh sau:

Tìm phần tử lớn nhất trong D, giả sử đó là D[i], ta đổi dấu của D[i] coi nh đánh
dấu nó, tìm tiếp phần tử j = T[i], lại đổi dấu D[j], quá trình cứ nh thế lùi chỉ số j
đến khi j=0

I 1 2 3 4 5 6 7 8 9 10 11 12

A[i] 6 12 8 11 3 4 1 7 5 9 10 2

T[i] 0 1 1 3 0 5 0 6 6 8 10 7

D[i] 1 2 2 3 -1 -2 1 -3 3 -4 -5 2

Kết qủa đợc dãy con dài nhất là : 3 4 7 9 10

Ch

ơng trình :
uses crt;

const max = 10000;
fi = 'BL1.INP';
fo = 'BL1.OUT';

type mang = array[1..max] of integer;
var a,d,t : mang;

n,dem : longint;
f : text;
procedure nhap;

</div>
(10)<div class='page_container' data-page=10>

fillchar(a,sizeof(a),0);
assign(f,fi);

reset(f);
readln(f,n);

for i:=1 to n do read(f,a[i]);
close(f);

end;

procedure khoitri;

begin

fillchar(t,sizeof(t),0);
t[1]:= 0;

d[1]:= 1;
end;

function vitri_truoc(i: longint): longint;
var j,ld,lj: longint;

begin

ld:= 0;
lj:= 0;

vitri_truoc:= 0;

for j:=i-1 downto 1 do

if a[j]<=a[i] then

if d[j]>ld then

begin

ld:= d[j];

lj:= j;

end;

vitri_truoc:= lj;
end;

procedure tao_td;
var i: longint;
begin

khoitri;

for i:=2 to n do
begin

</div>
(11)<div class='page_container' data-page=11>

if t[i]=0 then d[i]:= 1

else

d[i]:= d[t[i]]+1;

end;

function maxd: longint;
var i,p,li: longint;
begin

p := -maxint;

li := 0;

for i:=1 to n do

if d[i]>p then

begin

p := d[i];

li := i;

end;

maxd:= li;

end;

procedure timketqua;
var i: longint;
begin

i := maxd;
d[i] := -d[i];
dem := 1;
repeat

i:= t[i];

if i<>0 then

begin

d[i]:= -d[i];

inc(dem)

end;

until i=0;
end;

</div>
(12)<div class='page_container' data-page=12>

var f : text;

i : longint;

begin

assign(f,fo);
rewrite(f);
writeln(f,dem);
dem:= 0;

for i:= 1 to n do

if d[i]<0 then

begin

write(f,a[i]:7);

inc(dem);

if dem mod 10 = 0 then writeln(f);

end;

close(f);

end;
BEGIN

clrscr;
nhap;
tao_td;
timketqua;
ghi;

END.

Bµi 2:(D·y chung dµi nhÊt cña 2 d·y sè)

Cho 2 số nguyên dơng M, N (0<M, N<=100) và 2 dãy số nguyên: A1, A2,...,
AN và B1, B2,..., B M. Tìm một dãy dài nhất C nhận đợc từ A bằng cách xoá đi một
số số hạng và cũng nhận đợc từ B bằng cách xố đi một số số hạng (nói chung
khơng cùng chỉ số nh đối với dãy A). Ta gọi C là dãy con chung dài nhất của hai
dãy A và B.

Dữ liệu vào: File BL2.INP có cấu trúc nh sau:

+ Dßng thø nhÊt chøa N sè A1, A2,..., AN
+ Dòng thứ hai chứa M số B1, B2,..., B M.

Dữ liƯu ra : File BL2.OUT cã cÊu tróc nh sau:

</div>
(13)<div class='page_container' data-page=13>

+ Dòng thứ ba chứa k số là chØ sè trong d·y A cđa k sè h¹ng cđa C
+ Dòng thứ t chứa k số là chỉ số trong d·y B cđa k sè h¹ng cđa C

H

íng dÉn:

Cần xây dựng mảng C[1..N,1..M] với ý nghĩa: C[i,j] là độ dài của dãy chung
dài nhất của hai dãy A[1..i] và B[1..j]. Đơng nhiên C[1,j] = 0 nếu A[1] khơng có
trong dãy B, ngợc lại thì C[1,j] = 1. Tơng tự C[i,1] = 0 nếu B[1] không có trong
dãy A, ngợc lại thì C[i,1] = 1. Những trờng hợp cịn lại C[i,j] đợc tính theo cơng
thức truy hồi sau:

C[i,j] = Max{C[i,j-1],C[i-1,j],C[i-1,j-1]+x}
(mµ x=0 nÕu A[i]  B[j] và x=1 nếu A[i]=B[j])

Thật vậy:

Nếu A[i]=B[j] thì C[i,j] = C[i-1,j-1] +1
NÕu A[i]<>B[j] th×

+ NÕu A[i] trong B[1..j] th× nã chØ thuéc B[1 .. j-1] nªn C[i,j] = C[i,j-1]
+ NÕu B[j] trong A[1..i] th× nã chØ thuéc A[1 .. i-1] nên C[i,j] = C[i-1,j]

Ch

ơng trình :
uses crt;

const fi = 'BL2.INP';
fo = 'BL2.OUT';

type mang = array[1..100] of integer;

m2 = array[1..100,1..100] of integer;
var f : text;

a,b : mang;
nh : m2;
m,n : byte;
pa,pb : mang;
dem : byte;
procedure doc_file;
var f : text;
begin

</div>
(14)<div class='page_container' data-page=14>

assign(f,fi);
reset(f);

while not eoln(f) do
begin

inc(m);

read(f,a[m]);
end;

readln(f);

while not eoln(f) do
begin

inc(n);

read(f,b[n]);
end;

close(f);
end;

function thuoc(ch : integer;x : mang;k : byte) : boolean;
var i : byte;

begin

for i:=1 to k do
if ch = x[i] then
begin

thuoc := true;
exit;

end;

thuoc := false;
end;

function max(i,j,k : integer) : integer;
var p : integer;

begin

p := i;

if j>p then p := j;
if k>p then p := k;
max := p;

end;

</div>
(15)<div class='page_container' data-page=15>

var i,j : byte;
begin

for i:=1 to m do

if thuoc(b[1],a,i) then

nh[i,1] := 1 else nh[i,1] := 0;
for j:=1 to n do

if thuoc(a[1],b,j) then

nh[1,j] := 1 else nh[1,j] := 0;

for i:=2 to m do

for j:=2 to n do

nh[i,j] := max(nh[i-1,j-1]+ord(a[i]=b[j]),
nh[i,j-1],nh[i-1,j]);

writeln(f,'do dai 2 day sau khi xoa : ',nh[m,n]);
i := m;

j := n;

fillchar(pa,sizeof(pa),0);
fillchar(pb,sizeof(pb),0);
dem := 0;

while (i>0) and (j>0) do
begin

if a[i]=b[j] then
begin

inc(dem);
pa[dem] := i;
pb[dem] := j;
dec(i);

dec(j);
end

else

if nh[i,j]=nh[i,j-1] then dec(j)
else dec(i);

end;

for i:=dem downto 1 do write(f,a[pa[i]],' ');
writeln(f);

</div>
(16)<div class='page_container' data-page=16>

writeln(f);

for i:=dem downto 1 do write(f,pb[i],' ');
end;

BEGIN

clrscr;

assign(f,fo);
rewrite(f);
doc_file;
thuc_hien;
close(f);
END.

Bµi 3:(Di chun từ Tây sang Đông)

Cho hỡnh ch nhật MN ô vuông, mỗi ô chứa 1 số nguyên. Có thể di
chuyển từ 1 ơ sang ơ thuộc cột bên phải cùng dịng hoặc chênh lệch 1 dịng. Tìm

cách di chuyển từ một ô nào đó của cột 1 đến một ô nào đó thuộc cột n sao cho
tổng các số của các ụ i qua l nh nht.

Dữ liệu vào lấy từ file BL3.INP dòng đầu là 2 số nguyên dơng M, N. M
dòng tiếp theo mỗi dòng N số nguyên của hình chữ nhật.

Kết quả ghi ra file BL3.OUT gồm 2 dòng:
Dòng thứ nhất ghi tổng các số của các ô ®i qua.

Dòng thứ hai ghi N số là chỉ số dịng của các ơ đi qua từ cột 1 đến cột N.

H

íng dÉn:

Giả sử các số cho trong mảng A[1.. M,1.. N]. Dùng mảng F[1.. M,1.. N] để
xây dựng nhãn cho từng ô theo công thức truy hồi. F[i,j] có giá trị bằng tổng các
số trên các ô đi qua theo con đờng tốt nhất từ một ơ thích hợp thuộc cột 1 đến ô
(i,j) thuộc dòng i cột j.

Nhãn của các ô thuộc cột 1 bằng chính giá trị các ơ đó. Các ơ cịn lại, lần lợt từ cột
2 đến cột n đợc xây dựng theo công thức truy hồi sau:

F[i,k] := Min { F[i-1,k-1], F[i,k-1], F[i+1,k-1] } + A[i,k]

</div>
(17)<div class='page_container' data-page=17>

Cũng lu ý rằng có thể khơng cần dùng mảng F[1.. M,1.. N] bằng cách ghi
giá trị của F[1.. M,1.. N] đè dần lên mảng A[1.. M,1.. N] bắt đầu từ cột 2 đến cột
N.

uses crt;

const maxmn = 100;

fi = 'BL3.INP';
fo = 'BL3.OUT';

var a,t : array[0..maxmn,0..maxmn] of integer;
kq : array[1..maxmn] of byte;

m,n : byte;
procedure doc_file;
var f : text;
i,j : byte;
begin

assign(f,fi);
reset(f);
readln(f,m,n);
for i:=1 to m do
begin

for j:=1 to n do read(f,a[i,j]);
readln(f);

end;
close(f);
end;

function min(i,j : byte): byte;
var p : integer; d : byte;

begin

p := a[i-1,j-1];
d := i-1;

if a[i,j-1]<p then
begin

p := a[i,j-1];
d := i;

</div>
(18)<div class='page_container' data-page=18>

if a[i+1,j-1]<p then
begin

p := a[i+1,j-1];
d := i+1;

end;
min := d;
end;

procedure tao_nhan;
var i,j,d : byte;
begin

for j:=0 to n do a[0,j] := maxint;
for j:=0 to n do a[m+1,j] := maxint;
fillchar(t,sizeof(t),0);

for j:=2 to n do

for i:=1 to m do
begin

d := min(i,j);

a[i,j] := a[d,j-1] + a[i,j];
t[i,j] := d;

end;
end;

procedure tim_duong;
var i,j,d : byte;
p : integer;
f : text;
begin

p := maxint;
for i:=1 to m do
if a[i,n]<p then
begin

d := i;
p := a[i,n];
end;

</div>
(19)<div class='page_container' data-page=19>

i := d;
kq[j] := d;
assign(f,fo);
rewrite(f);

writeln(f,a[i,j]);
while j>0 do

begin

i := t[i,j];
j := j-1;
kq[j] := i;
end;

for j:=1 to n do write(f,kq[j],' ');
close(f);

end;
BEGIN

doc_file;
tao_nhan;
tim_duong;
END.

Bµi 4a: (XÕp va li)

</div>
(20)<div class='page_container' data-page=20>

Dữ liệu vào lấy từ file văn bản VALY.INP gồm ba dòng
Dòng thứ nhất là N và W

N dßng tiÕp theo: dßng i+1 ghi hai sè: A[i] và C[i] (i=1,2,..N), hai số cách
nhau bởi dấu cách.

Kết quả ghi ra file văn bản VALY.OUT theo quy cách sau:
Dòng thứ nhất là tổng giá trị lớn nhất của va ly

Các dòng tiếp theo mỗi dòng 2 số: số i (số hiệu vật đợc chọn) và số x (số lợng
chọn vật i)

VÝ dô:

Valy.inp

4 100
50 50
19 20
80 90
21 25

valy.out

110
2 1
3 1

H

íng dÉn:

a) Tỉ chøc d÷ liƯu:

 Hai mảng một chiều g1 và g2: g1[y] là tổng giá trị các vật đã đợc chọn khi
trọng lợng còn thiếu của va ly là y và vừa xét xong đồ vật có số hiệu lẻ,

g2[y] có ý nghĩa tơng tự khi vừa xét xong đồ vật có số hiệu chẵn.

 Hai mảng một chiều v1 và v2: v1[y] là số hiệu đồ vật đợc chọn cuối cùng
khi trọng lợng còn thiếu của va ly là y và vừa xét xong vật có số hiệu lẻ,
v2[y] là số hiệu đồ vật đợc chọn cuối cùng khi trọng lợng còn thiếu của va
ly là y và vừa xét xong vật có số hiệu chẵn.

b) Thực hiện: Để diễn đạt khi không phân biệt g1, g2 ta tạm dùng ký hiệu g,
không phân biệt v1, v2 ta dùng ký hiệu v.

</div>
(21)<div class='page_container' data-page=21>

 Sau đó xét chọn tiếp các đồ vật từ số hiệu k=2 đến n cho vào va ly còn thiếu
trọng lợng y nếu thấy lợi theo cơng thức gán nhãn sau:

 Tìm kết quả: nếu N chẵn thì lần ngợc theo g2 và v2, nếu N lẻ theo g1 và v1.
Kết quả số hiệu các đồ vật cho vào va ly đợc ghi nhận vào mảng một chiều
x: với ý nghĩa x[j] là số lợng đồ vật có số hiệu j đợc chọn vào va ly.

Ghi chú: Tuy nhiên bài toán này còn có thể giải bằng thuật toán có hiệu quả hơn 
về thời gian thùc hiƯn cịng nh kÝch thíc bé nhí so với thuật toán vừa nêu (xem 
ch-ơng xếp lịch công việc)

Ch

ơng trình:

uses crt;

const fi = 'valy.in3';
fo = 'valy.ou3';
var

a, {Träng lỵng vËt i : a[i]}

c, {Giá trị vật i : c[i]}

w, {Trọng lợng tối đa của va ly}
n : longint; {Số đồ vật}

sum_max : longint; {Tổng giá trị chọn đợc}

g1,g2:array[0..1500] of integer; {Theo rõi tổng giá trị chọn}
v1,v2:array[0..10000] of integer; {Sè hiÖu vËt chän}

</div>
(22)<div class='page_container' data-page=22>

procedure input;
var f : text;
i : integer;
begin

assign(f,fi);
reset(f);
readln(f,n,w);
for i:=1 to n do

read(f,a[i],c[i]);
close(f);

end;

function max(a,b:longint):longint;
begin

if a>=b then max:=a
else max:=b;

end;

procedure tinh2(k,y:integer);{k=2,4,6,..-> t¹o g2 tõ g1, v2 tõ v1}

begin

if a[k]>y then

g2[y]:=g1[y] {không chọn vật k, g2 lấy lại giá trị g1}
else

g2[y]:=max(c[k]+g2[y-a[k]], g1[y]);{cã thÓ chän k, hoặc không}
if g1[y]=g2[y] then {không chọn vËt k}

v2[y]:=v1[y]; {ghi l¹i vËt chän ë bíc tríc}
if g1[y]<g2[y] then {chän vËt k}

v2[y]:=k; {ghi l¹i vËt vừa chọn là k}
end;

procedure tinh1(k,y:integer);{k =3,5,7..-> tạo g1 từ g2, v1 từ v2}
begin {quá trình tơng tự thủ tục trên}

if a[k]>y then g1[y]:=g2[y]
else

</div>
(23)<div class='page_container' data-page=23>

procedure qhd;

var i,k,y,cs,s,j:integer;
begin

(* Khëi t¹o *)
g1[0] := 0;
g2[0] := 0;
v1[0] := 0;
v2[0] := 0;

for i:=1 to w do {các khả năng về trọng lợng cßn thiÕu cđa va ly}
begin

g1[i] := c[1]*(i div a[1]);
if g1[i] >0 then

v1[i] := 1{chän vật 1, số lợng là i div a[1]}
else v1[i]:=0;

end;

for k:=2 to n do {XÐt chän c¸c vËt tõ 2->n}
begin

if (k mod 2)=0 then

for y:=1 to w do tinh2(k,y)

{Khi va ly còn thiếu trọng lợng y, xét chọn vật k chẵn, xây dựng g2,v2}

else

for y:=1 to w do tinh1(k,y);

{Khi va ly còn thiếu trọng lợng y, xét chọn vật k lẻ, xây dựng g1,v1}
end;

(* Tìm ngợc: tìm phơng án tối u *)
for i:=1 to n do x[i]:=0;
s:=w;

if (n mod 2)=0 then {NÕu n ch½n thì dựa vào g2,v2}
begin

repeat

j := v2[s];
x[j] := x[j]+1;
s := s-a[j];
until v2[s]=0;

</div>
(24)<div class='page_container' data-page=24>

end

else {Nếu n lẻ thì dựa vào g1,v1}
begin

repeat

j := v1[s];
x[j] := x[j]+1;

s := s-a[j];
until v2[s]=0;

sum_max:=g1[w];
end

end;

procedure inkq;
var i : integer;
f : text;
begin

assign(f,fo);
rewrite(f);
for i:=1 to n do
if x[i]>0 then

writeln(f,i:4,{a[i]:4,c[i]:4,}x[i]:4);
writeln(f,sum_max);

close(f);
end;

BEGIN

clrscr;
input;
qhd;
inkq;

END.

Phơng pháp 2: Phân rÃ bài toán thành hai bài toán con:

H

íng dÉn:

</div>
(25)<div class='page_container' data-page=25>

Khi va ly thứ hai có trọng lợng là 0 thì ta hiểu là khơng thể phân chia va ly
thứ nhất đợc nữa, hay nói cách khác lúc đó va ly có trọng lợng tối đa bằng K chỉ
chứa 1 vật có giá trị tốt nhất mà trọng lợng vật này là K.

Vậy bằng cách chia nhỏ dần các va ly ta sẽ tìm đợc các va ly khơng thể chia
nhỏ đợc nữa, đó chính là các va ly mà mỗi cái đựng 1 vật có giá trị tốt nhất bên
trong nó. Tập hợp các va ly này chính là tập các vật cho vào va ly ban đầu trong
phơng án tốt nhất.

VỊ tỉ chøc dữ liệu và thực hiện:

To mng L vi kớch thc bằng trọng lợng tối đa W. L[K] cho giá trị tối u
của va ly có trọng lợng khơng lớn hơn K. Khởi trị L: tìm đồ vật i0 trong các đồ vật
có trọng lợng  W0 , có giá trị tốt nhất, ghi nhận L[W0] := C[i0],

Đồng thời dùng mảng p1(W) để ghi nhận số hiệu của các đồ vật i0 nêu trên:
p1[W0]=i0. Mảng p2(W) để ghi nhận đồ vật i0 không thể phân chia đợc nữa:
p2[w0]=0 (sau đây ta sẽ dùng p1 và p2 với ý nghĩa khác nhng không mâu thuẫn với
ý nghĩa vừa trình bày).

Trong quá trình phân chia va ly, ta xây dựng nhãn của va ly có trọng lợng tối
đa là k theo công thức quy hoạch động sau:

L[k] := Max { L[k], L[i] + L[k-i]  k=1,..n,  i= (k div 2),..,k-1,k }

Khi thực hiện công thức trên đồng thời với xây dựng mảng L, ta cũng xây
dựng mảng p1 và p2 : p1[k]:= i; p2[k] := k-i nghĩa là xác nhận nếu chọn phơng án
tối u cho va ly có trọng lợng tối đa bằng k thì nó đợc phân chia thành 2 va ly, một
cái có trọng lợng tối đa là i, cái kia có trọng lợng tối đa là k-i. Nếu k-i=0 thì va ly
thứ nhất (trọng lợng tối đa là i) là phơng án tối u mà đã khởi trị ban đầu (rõ ràng
giá trị mới của p1[i] là i không đợc ghi đè lên giá trị cũ của nó là số hiệu của va ly
tốt nhất có trọng lợng bằng i vì việc ghi đè này chỉ tiến hành sau khi va ly i có thể
phân chia đợc thành 2 va ly cựng cú trng lng khỏc 0).

Rõ ràng cách giải thứ hai nhiều thuận lợi hơn cách thứ nhất.

Ch

ơng trình:

uses crt;

const mv = 2000; {max so loai do vat}
mw = 6000; {max trong luong}
fi = 'valy.in1';

fo = 'valy.ou1';

</div>
(26)<div class='page_container' data-page=26>

L : array[0..mw] of longint;
n,w : integer;

procedure tao_test;

var f : text;
i : integer;
x,y : integer;
begin

assign(f,fi);
rewrite(f);

writeln(f,mv,' ',mw);
for i:=1 to mv do
begin

x := 50+random(100);
y := 100+random(100);
writeln(f,x,' ',y);
end;

close(f);
end;

procedure doc_file;
var f : text;
i : integer;
begin

assign(f,fi);
reset(f);
readln(f,n,w);

for i:=1 to n do read(f,a[i],c[i]);

close(f);

end;

function tim(x : integer; var i : integer):integer;
var j,p : integer;

begin

p := 0; i := 0;
for j:=1 to n do

</div>
(27)<div class='page_container' data-page=27>

p := c[j];
i := j;
end;

tim := p;
end;

procedure khoi_tri;
var i,x : integer;
begin

fillchar(p1,sizeof(p1),0);
fillchar(p2,sizeof(p2),0);
fillchar(L,sizeof(L),0);
for x:=1 to w do

begin

L[x] := tim(x,i);
p1[x] := i;

end;
end;

procedure phan_ra(k : integer);
var i : integer;

begin

for i:= k downto (k+1) div 2 do
if L[i]+L[k-i]>L[k] then

begin

L[k] := L[i] + L[k-i];

p1[k] := i; {va ly träng lỵng k, chia thành va ly con 1 trọng lợng i}
p2[k] := k-i; {va ly trọng lợng k, chia thành va ly con 2 träng lỵng k-i}
end;

end;

procedure timkq(k : integer);
var i,j : integer;

begin

i := p1[k]; j := p2[k];

if (j=0) then inc(dd[i]) {va ly i = vật i đợc chọn}
else

</div>
(28)<div class='page_container' data-page=28>

timkq(j);
timkq(i);
end

end;

procedure thuc_hien;
var i,j : integer;
f : text;
begin

for i:= 1 to w do phan_ra(i);
j := 1;

for i:=1 to w do

if L[i]>L[j] then j := i;
assign(f,fo); rewrite(f);
writeln(f,L[j]);

timkq(w);

for i:=1 to n do

if dd[i]>0 then writeln(f,i:5,' ',dd[i]);
close(f);

end;
BEGIN

tao_test;
doc_file;
khoi_tri;
thuc_hien;
END.

Bài 4b: (Xếp va li, mỗi đồ vật chỉ có một cái)

Cho một va ly có thể chứa W đơn vị trọng lợng. Có N đồ vật, đồ vật i có trọng
lợng A[i] và có giá trị là C[i]. Hãy xếp đồ vật vào va ly để tổng giá trị ca va ly l
tt nht.

Dữ liệu vào lấy từ file văn bản VALY.INP gồm ba dòng
Dòng thứ nhất là N và W

N dòng tiếp theo: dòng i+1 ghi hai sè sè A[i] vµ C[i] (i=1,2,..n), hai sè c¸ch
nhau bëi dÊu c¸ch.

</div>
(29)<div class='page_container' data-page=29>

 Dịng thứ nhất là tổng giá trị lớn nhất của các đồ vật đợc chọn

 Các dòng tiếp theo mỗi dòng 3 số là số hiệu, trọng lợng, giá trị vật đợc chọn

VÝ dô:

Valy.inp

3 10
1 70
5 300
5 300

valy.out

600
2 5 300
3 5 300

H íng dÉn:

Bài xếp va ly b) khác bài xếp va ly a) ở chỗ mỗi loại đồ vật chỉ có 1 cái. Có thể giải
nh sau:

a) Tổ chức dữ liệu: Mảng hai chiều L(N,W): L[i,j] là giá trị của va ly khi trọng
lợng max của va ly là j và xét xong từ vật 1 đến vật i.

b) Khëi trÞ L[0,j]=0; j: 0<j<=w, L[i,0]=0;  i: 0<i<=N
c) Xây dựng nhÃn L[i,j] theo công thức

L[i,j] = Max(L[i-1,j], L[i-1,j-A[i]] + C[i]) nÕu A[i]j
Hc L[i,j] = L[i-1,j] nÕu A[i]>j

</div>
(30)<div class='page_container' data-page=30>

Ch

ơng trình:

uses crt;

const maxn = 100;
maxw = 1000;

fi = 'valy.in2';
fo = 'valy.ou2';

type m1 = array[0..maxw] of word;
m2 = array[0..maxn] of ^m1;
var L : m2;

a,c : array[1..maxn] of word;
n,w : word;

procedure doc_file;

var f : text; i : word;
begin

assign(f,fi); reset(f);
readln(f,n,w);

fillchar(a,sizeof(a),0);
c := a;

for i:=1 to n do read(f,a[i],c[i]);
close(f);

end;

function max(v1,v2 : word): word;
begin

if v1>v2 then v2 := v1;
max := v2;

end;

procedure xuly;

var i,j : word ;
begin

for i:=0 to n do
begin

new(L[i]);

</div>
(31)<div class='page_container' data-page=31>

for i:=1 to n do
for j:=1 to w do
begin

if a[i]<=j then
L[i]^[j]:=

max(L[i-1]^[j-[i]]+c[i],L[i]^[j])
else L[i]^[j] := L[i-1]^[j];

end;

procedure ghi_file;

var vmax,v0,n0,i,j : word;
f : text;

begin

assign(f,fo); rewrite(f);

vmax := 0; v0 := 0; n0 := 0;
for j:=1 to w do

if vmax<L[n]^[j] then
begin

vmax := L[n]^[j];
v0 := j;

end;
j := v0;

writeln(f,vmax);
for i:=n downto 1 do

if L[i]^[j]<>L[i-1]^[j] then
begin

inc(n0);

writeln(f,i,' ',a[i],' ',c[i]);
j := j - a[i];

end;
close(f);
end;

BEGIN

</div>
(32)<div class='page_container' data-page=32>

ghi_file;
END.

Bài 5: Biến đổi xâu:

Với một xâu ký tự S cho trớc, ta có thể thực hiện các phép biến đổi sau:
 D: xoá một ký tự của xâu S. Ký hiệu D i mà i là vị trí ký tự cần xố.

 I: chèn trớc vị trí t của xâu S một ký tự c nào đó. Ký hiệu I t c. Quy định thêm
về vị trí chèn: nếu xâu S có độ dài K, vị trí chèn có thể là 1, 2, 3, ..., k+1 mà chèn ở
vị trí k+1 có nghĩa là viết thêm vào cuối xâu S.

 R: thay ký tự thứ t của S bởi ký tự c nào đó. Ký hiệu R t c.

 Giả sử X và Y là hai xâu ký tự. Độ dài xâu X là N, độ dài xâu Y là M. Hãy tìm một
dãy gồm ít nhất các phép biến đổi biến xâu X thành xâu Y.

Số phép biến đổi ít nhất gọi là khoảng cách giữa hai xâu.

D÷ liệu vào ghi trong file QHD05.INP gồm hai dòng: Dòng thứ nhất là xâu X,

dòng thứ hai là xâu Y

Kết qu¶ ghi ra file ‘QHD05.OUT’:

+ Dịng thứ nhất là số K, đó là khoảng cách hai xâu

+ K dịng tiếp theo mỗi dòng ghi ký hiệu một phép biến đổi theo trình tự thực hiện để
biến X thành Y

VÝ dô:
QHD05.INP
ertrtyui
tyuhj

QHD05.OUT
6

</div>
(33)<div class='page_container' data-page=33>

I h 4
R 5 j

H

ớng dẫn: Gọi L[i,j] là số lợng ít nhất các phép biến đổi (chèn, xoá, thay thế) để biến
xâu con x1x2...xj thành xâu con y1y2...yi

Nếu xj =yi thì L[i,j]=L[i-1,j-1] vì chỉ cần biến đổi x1x2...xj-1 thành y1y2...yi-1 thì
x1x2...xj sẽ biến thành y1y2...yi

 Nếu xj<>yi xét 3 khả năng biến đổi :

 Xoá xj của X và biến đổi x1x2...xj-1 thành y1y2...yi, số biến đổi là L[i, j-1]+1

 Biến đổi x1x2...xj thành y1y2...yi-1 rồi chèn yi vào X sau yi-1, số biến đổi là
L[i-1,j]+1

 Biến đổi x1x2...xj-1 thành y1y2...yi-1 rồi thay xj của X bởi yi, số biến đổi l
L[i-1,j-1]+1

Công thức truy hồi chung cho trờng hợp xi<>yj lµ:

L[i,j] := min(L[i-1,j]+1,L[i,j-1]+1,L[i-1,j-1]+1)
Ngoài ra lu ý khởi trị mảng L[0..M,0..N] nh sau:

L[0,j]=j 0 j  N vì phải xố j ký tự của X để thành xâu rỗng Y
L[i,0]=i 0 i  M vì phải chèn i ký tự của Y vào xâu rỗng X.

Sau khi có bảng L[0..m,0..n] dùng nó để tìm ra các phép biến đổi.
L[m,n] là số phép biến đổi cần tìm. Điểm bắt đầu tìm kiếm là điểm (M,N).
Từ điểm (i,j) trong bảng ta tìm các điểm tiếp theo dựa vào nhận xét:

L[i,j]= L[i-1,j]+1 lµ dïng phÐp I (chÌn)
L[i,j]= L[i,j-1]+1 lµ dïng phép D (xoá)
L[i,j]= L[i-1,j-1]+1 là dùng phép R (thay)

Trong quỏ trình tìm, ghi lu toạ độ (vị trí) của các điểm này vào hai mảng một chiều d và
c để biết tại điểm tìm đợc ta đang xét vị trí nào trên X ban đầu và vị trí nào trên Y.

Ch

ơng trình

uses crt;

const max = 254;

fi = 'kc10.in';
fo = 'output.txt';

</div>
(34)<div class='page_container' data-page=34>

l : ^m2;
d,c : m1;
m,n : byte;
procedure input;

var f :text;
begin

assign(f,fi);
reset(f);
readln(f,x);
readln(f,y);
close(f);
end;

function min(u,v:byte):byte;
begin

if u>v then min:=v else min := u;
end;

procedure solution;

var i,j,k :byte;
begin

n:=length(x); m:=length(y);
for k:=0 to n do l^[0,k]:=k;
for k:=0 to m do l^[k,0]:=k;
for j:=1 to n do

for i:=1 to m do
if x[j]=y[i] then

l^[i,j]:=l^[i-1,j-1]
else

begin

</div>
(35)<div class='page_container' data-page=35>

end;
end;

procedure output;
var f :text;

i,j,k : integer;

t : integer; {độ dài thêm của X hiện thời so với X ban đầu}
begin

assign(f,fo);
rewrite(f);

writeln(f,l^[m,n]);
fillchar(d,sizeof(d),0);
fillchar(c,sizeof(c),0);
k := 0;

i := m;
j := n;
repeat

inc(k);

d[k] := i;{vị trí đang xét trên Y, khi thực hiện phép biến đổi thứ k}
c[k] := j; {vị trí đang xét trên X, khi thực hiện phép biến đổi thứ k}
if (i>0) and (j>0) then

begin

if x[j]=y[i] then
begin

dec(i);
dec(j);
end

else

{if x[j]<>y[i] then }
begin

if l^[i,j]=l^[i-1,j-1]+1 then

begin

</div>
(36)<div class='page_container' data-page=36>

else

if l^[i,j]=l^[i,j-1]+1 then dec(j)
else

if l^[i,j]=l^[i-1,j]+1 then dec(i);
end;

end{ het i>0 and j>0}
else

begin

if (i>0) then dec(i)
else dec(j);

end;

until (i=0) and (j=0);
inc(k);

d[k] := 0;
c[k] := 0;
t := 0;
la := x;

for i:= k downto 2 do
begin

if c[i]=c[i-1] then
begin

writeln(f,'I: y[',d[i-1],'] ',c[i]+1+t);
insert(y[d[i-1]],la,c[i]+1+t);

inc(t);
writeln(la);
end;

if d[i]=d[i-1] then
begin

writeln(f,'D: x[',c[i-1]+t,']');
delete(la,c[i-1]+t,1);

dec(t);
writeln(la);
end;

</div>
(37)<div class='page_container' data-page=37>

begin

writeln(f,'R: x[',c[i-1]+t,'] y[',d[i-1],']');
la[c[i-1]+t]:=y[d[i-1]];

end;
end;
close(f);
end;

BEGIN

new(l); fillchar(l^,sizeof(l^),0);
input;

solution;
output;
dispose(l);
END.

Bµi 6: (Nh©n ma trËn)

Xét tích các ma trận: M=M1.M2.. MN. Kích thớc các ma trận đợc cho bởi mảng
D=(d0, d1,.., dN): ma trận Mi có kích thớc là di-1di (di-1 dịng và di cột). Dùng tính chất
kết hợp của ma trận, hãy nêu cách tính M với số lợng phộp nhõn ớt nht.

Dữ liệu vào lấy từ file QHD04.INP gồm:

dòng thứ nhất là số N

dòng thứ hai là N+1 số d0, d1,... , dn

Kết quả ghi ra file QHD04.OUT gồm:

dòng thứ nhất là số lợng phÐp nh©n Ýt nhÊt

 dịng thứ hai là biểu diễn tích M sau khi đã chèn các dấu ngoặc tối thiểu cần dùng.

VÝ dô:

QHD04.INP
4

13 5 89 3 34

QHD04.OUT
2856

</div>
(38)<div class='page_container' data-page=38>

H

íng dÉn : C[i , j]=

∑

k=1
N

A[i , k].B[k , j] Ma trận là mảng hai chiều. Phép nhân ma trận
khơng giao hốn nhng kết hợp: với 3 ma trận A, B, C nhân đợc với nhau ta có
A(BC)=(AB)C. Điều kiện để có thể nhân ma trận A với ma trận B là số cột của A phải
bằng số dòng của B. Nếu A có M dịng N cột và B có N dịng P cột thì ma trận tích
C=AB có M dịng P cột và phần tử dòng i cột j của C đợc tính bằng cơng thức:

Nh vậy, để nhân A với B ta cần thực hiện M.N.P phép nhân. Khi chạy máy tính, thời
gian thực hiện phép nhân lớn hơn phép cộng. Do đó khi nhân nhiều ma trận với nhau
nếu thu xếp khéo trình tự nhân, ta có thể giảm đáng kể số phép nhân.

Khi tính tích M=M1.M2... MN trong đó Mi là các ma trận sao cho hai ma trận liên
tiếp trong tích có thể nhân với nhau. Phép nhân ma trận có tính chất kết hợp, do vậy có
nhiều cách thực hiện M=(...((M1.M2)M3)... MN) hoặc M=(M1(M2(M3... (MN-1MN)...)))
v ...v. Ta có thể thấy với mỗi cách quy định các dấu ngoặc, số phép nhân nói chung khác
nhau.

Ví dụ xét tích ABCD của 4 ma trận với kích thớc A(13,5), B(5,89), C(89,3), D(3,34). Để
biết hiệu quả của các cách tính khác nhau chúng ta tính số lợng các phép nhân đợc thực
hiện trong mỗi cách. Có 5 cách tính khác nhau:

((AB)C)D 10.582 số phép nhân phải thực hiện

(AB)(CD) 54.201

(A(BC))D 2.856

A((BC)D) 4.055

A(B(CD)) 26.418

Phơng pháp hiệu quả nhất coi nh nhanh hơn 19 lần so với cách chậm nhất.
T(N)=

i=1
n 1

T(i).T(N i) Có thể trực tiếp tìm ra cách tốt nhất bằng cách đặt các
biểu thức trong ngoặc đơn theo các kiểu có thể và tính số lần thực hiện các phép nhân.
Số các cách khác nhau để đặt ngoặc cho tích n ma trn l s Catalan T(N).

Nhận thấy T(N) tăng rất nhanh khi n tăng, T(1)=1,.. T(15) =2674440 nên phơng
pháp tính trực tiếp này không có khả năng hiện thực khi N lín.

Nguyên lý quy hoạch động sẽ đợc áp dụng vào bài toán này: Nếu cách tốt nhất của
phép nhân tất cả các ma trận đòi hỏi chúng ta tạo ngoặc phân cách giữa ma trận thứ i và
i+1 của tích thì cả hai phần M1M2..Mi và Mi+1Mi+2..MN cần phải đợc tính theo cách tối u.

Chúng ta xây dựng bảng M[1...N,1...N] ở đây Mij, cho số ít nhất các phép nhân để tính
tích MiMi+1..Mj (Nh vậy thực chất ta chỉ tính Mij với ij).

</div>
(39)<div class='page_container' data-page=39>

Biết kích thớc của các ma trận Mi cho bởi véc tơ di (0  i  N), ma trận Mi có kích
thớc di-1 và di. Chúng ta xây dựng dần bảng mij theo từng đờng chéo. Đờng chéo s gồm
những phần tử mij mà j-i=s. Chúng ta có:

s=0: mii = 0 i=1,2,..,N
s=1: mi i+1 = di-1 di di+1 i=1,2,..,N-1

1<s<N: mi,i+s = min (mi,k + m k+1, i+s+di-1 dk di+s) i=1,2..,N-s
i  k < i+s

Trờng hợp cuối có nghĩa là: để tính Mi.Mi-1....Mi+s chúng ta đã thử tất cả các cách
(MiMi+1..Mk)(Mk+1,..,Mi-s) và chọn cách tốt nhất, i  k < i+s.

VÝ dơ: Chóng ta cã d=(13,5,89,3,34)

Víi s=1 chóng ta cã

m12=d0.d1.d2=13.5.89 =5785
m23= d1.d2.d3=5.89.3 =1335
m34= d2.d3.d4=89.3.34 =9078
víi s=2 chóng ta cã

m13=min(m11+m23+1353, m12 + m33 + 13893)=min(1530,9256)=1530
m24=min(m22+m34+58934, m23 + m44 + 5334)=min(24208,1845)=1845
víi s=3

m14=min(m11+m24+13534,m12+m34+138934,m13+m44+13334)

=min(4055,54201,2856)=2856

Vậy mảng M đợc cho trong hình sau:

J=1 J=2 J=3 J=4

I=1 0 5785 1530 2856

I=2 0 1335 1845

I=3 0 9078

I=4 0

Ch

ơng trình

Const fi = 'bl1.inp';
fo = 'bl1.out';
maxn = 50;

Type mang1 = array[0..maxn] of comp;
mang2 = array[0..maxn] of byte;

s=2

s=1

s=0

</div>
(40)<div class='page_container' data-page=40>

var f : text;
n : integer;

L : array[0..maxn] of mang1;
t : array[0..maxn] of mang2;

p : array[1..maxn,1..2] of integer;
d : mang1;

procedure input;

var i:integer;
begin

assign(F,fi); reset(f);
readln(F,n);

for i:=0 to n do
read(f,d[i]);
close(f);

end;
procedure init;

var i:integer;
begin

fillchar(L,sizeof(L),0);

fillchar(t,sizeof(t),0);
for i:=1 to n-1 do

begin

L[i,i+1]:=d[i-1]*d[i]*d[i+1];
end;

end;

procedure qhd(i,j:integer);
var k,lk:integer;
min,tg:comp;
begin

min:=10e16;

for k:=i to j-1 do
begin

</div>
(41)<div class='page_container' data-page=41>

begin

min:=tg;
lk:=k;
end;

end;
L[i,j]:=min;
t[i,j]:=lk;
end;

procedure solution;

var i,j:integer;
begin

for i:=1 to n do

for j:=i-2 downto 1 do
qhd(j,i);

end;

procedure back(i,j:integer);
var tg:integer;
begin

if i<>j then
begin

inc(p[i,1]);
inc(p[j,2]);
end;

if (j-i<=1) then exit;
tg:=t[i,j];

back(i,tg);
back(tg+1,j);
end;

procedure output;

var i,j:integer;
begin

assign(f,fo); rewrite(f);
writeln(f,L[1,n]:0:0);

</div>
(42)<div class='page_container' data-page=42>

dec(p[1,1]);
dec(p[n,2]);
for i:=1 to n do
begin

for j:=1 to p[i,1] do write(f,'(');
write(f,char(i+64));

for j:=1 to p[i,2] do
write(f,')');
end;

close(f);
end;

BEGIN

input;
init;
solution;
output;

END.

Bài 7: (Chia đa giác) Cho một đa giác lồi N đỉnh, biết toạ độ các đỉnh. Bằng các đờng
chéo khơng có điểm chung (trừ trờng hợp điểm chung đó là đỉnh) hãy phân chia đa giác
đó thành các tam giác sao cho tổng độ dài các đờng chéo cần dùng là nhỏ nhất. Dữ liệu
vào lấy từ file ‘CHIA_DG.INP’ dòng đầu là số N, N dòng sau mỗi dịng là 2 số xi yi thể
hiện hồnh độ và tung độ đỉnh thứ i. Kết quả ghi ra file ‘CHIA_DG.OUT’ dòng đầu là
tổng độ dài các đờng chéo dùng chia đa giác, các dòng sau mỗi dòng là 2 số hiệu của 2
đỉnh đa giác là đầu của một đờng chéo đã dùng.

H

íng dÉn:

 Đánh số N đỉnh đa giác theo thứ tự là 0,1, ..., N-1. Và coi đỉnh M (MN) là đỉnh M
mod N. Mặt khác để đỡ phức tạp ta coi đờng chéo là đoạn thẳng nối hai đỉnh bất kỳ
của đa giác (cạnh coi là đờng chéo có độ dài = 0). Đồng thời đờng chéo nối đỉnh i
với đỉnh j cũng là đờng chéo nối đỉnh j với đỉnh i, nên khơng mất tính chất tổng qt
khi xét các đờng chéo xuất phát từ đỉnh i (i=0,1,..,n-1) chỉ cần nối đỉnh i với các đỉnh
(i+1) mod n, (i+2) mod n, ..., (i+n-1) mod n.

</div>
(43)<div class='page_container' data-page=43>

Ta xét các lớp đa giác có p+1 đỉnh (p=0, .., n-1), đỉnh đầu tiên là q (q=0, 1,..,
N-1) các đỉnh tiếp theo là (q+N-1) mod N, (q+2) mod N, .., (q+p) mod N. Ta gọi lớp đa
giác này vắn tắt là lớp (q,p)

Với mỗi đa giác thuộc lớp (q,p), ta tìm một đờng chéo nối đỉnh q với đỉnh (q+i) mod
N (i=1, 2,.., p-1) sao cho đa giác đợc chia thành hai đa giác con: đa giác thứ nhất có
đỉnh đầu là q, đỉnh cuối (tính theo chiều kim đồng hồ) là (q+i) mod N, đa giác thứ
hai có đỉnh đầu là (q+i) mod N và đỉnh cuối là (q+p) mod N, khi đó tổng các đ ờng
chéo dùng để chia đa giác này sẽ bằng tổng các đờng chéo chia đa giác thứ nhất

cộng với tổng các đờng chéo chia đa giác thứ hai cộng thêm đờng chéo nối đỉnh q
với đỉnh (q+p) mod N.

Giá trị tốt nhất của bài toán này khi xét các đa giác thuộc lớp (q,p) ghi l u vào
mảng A, với ý nghĩa A[q,p] là tổng nhỏ nhất các đờng chéo để chia các đa giác lớp
(q,p), đồng thời KQ[q,p] nhận giá trị i tơng ứng với cách chia tốt nhất.

 Khởi trị:q=0, 1,.., N-1: A[q,0]=0 ( vì i=0 đa giác là 1 đỉnh q)
A[q,1]=0 (vì i=1 “đa giác” chỉ có 2 đỉnh q, (q+1) mod N)

A[q,2]= độ dài đoạn nối đỉnh q với đỉnh (q+2) mod N (vì i=2 “đa giác” chỉ có 3
đỉnh q, (q+1) mod N, (q+2) mod N)

Các trờng hợp còn lại: p: 3pN-2, q: 0qN-1

A[q,p] = MIN { A[q,i] + A[(q+i) mod N, p-i ] + KC (q, q+p) }
(i = 1,2,..,p-1)

Lần ngợc mảng KQ tìm kết quả nh sau:

Trc ht tỡm trong mảng A(N,2) phần tử nhỏ nhất ở cột 2, thí dụ là A[q0,
N-2], đó là giá trị tổng nhỏ nhất các đờng chéo chia đa giác N đỉnh đã cho thành các tam
giác. Nhát chia đầu tiên là đờng chéo nối đỉnh q0 với đỉnh q0+i (i=KQ[q0, N-2]). Sau đó
theo dõi 2 đa giác nhỏ đã đợc chia... quá trình tìm i mới lại tiến hành trên 2 đa giác nhỏ
này. Q trình tìm kiếm này có thể tổ chức thực hiện đợc nhờ stack s (xem chơng trỡnh).

Ch

ơng trình:

uses crt;
const max = 50;

fi = 'chia_dg.inp';
fo = 'chia_dg.out';

</div>
(44)<div class='page_container' data-page=44>

g : m2;
nh : m1;
n : byte;
procedure nhap;
var i : byte;
f : text;
begin

assign(f,fi); reset(f);
readln(f,n);

for i:=0 to n-1 do readln(f,x[i],y[i]);
close(f);

end;

function kc(i,j : byte) : real;
begin

i := i mod n; j := j mod n;

kc := sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
end;

procedure khoitao;
var i : byte;
begin

for i:= 0 to n-1 do
begin

nh[i,0] := 0; nh[i,1] := 0;
nh[i,2] := kc(i,i+2);

end;
end;

procedure xuly;

var p,q,i,l,top : byte;
min : real;

s : array[1..max] of record d,t : byte end;
f : text;

begin

</div>
(45)<div class='page_container' data-page=45>

min := 1e+32; L := 0;

for i:= 1 to p-1 do {chon dinh trung gian la i}
if nh[q,i]+nh[(q+i) mod n,p-i]<min then

begin

min := nh[q,i]+nh[(q+i) mod n,p-i];
L := i;

end;

nh[q,p] := min + kc(q,q+p);
g[q,p] := L;

end;

assign(f,fo);
rewrite(f);

min := nh[0,n-2];
L := 0;

for i:= 1 to n-2 do
if nh[i,n-2]<min then

begin min := nh[i,n-2]; L := i; end;
writeln(f,min:10:2);

top := 1;
s[top].d := l;
s[top].t := n-2;
while top>0 do
begin

q := s[top].d; p := s[top].t;
dec(top);

writeln(f,q,' - ',(q+p) mod n);
if g[q,p]<>0 then

begin

s[top+1].d := q;
s[top+1].t := g[q,p];
if g[q,p]<>1 then inc(top);
s[top+1].d := (q+g[q,p]) mod n;
s[top+1].t := p - g[q,p];

</div>
(46)<div class='page_container' data-page=46>

end;
close(f);
end;

BEGIN
nhap;
khoitao;
xuly;
END.

IV - Các Bài tập luyện tập

1. Đề bài

Bi 1:(Hm Ackerman) Hm Ackerman c xác định nh sau:
¿

A(0, n)=n+1

A(m ,0)=A(m −1,1)¿khi¿m>0
A(m , n)=A(m −1, A(m , n1))khim , n>0

{ {

Hiện giá trị của A(m,n) trên màn hình khi

m,n là số nguyên không âm nhập tõ bµn phÝm.

Bài 2 : (Kiến leo quanh ống trụ) Cho bảng hình chữ nhật m dịng n cột gồm m*n ô,
mỗi ô chứa một số nguyên. Ngời ta cuộn hình chữ nhật lại thành hình trụ sao cho mép
trên và mép dới của hình chữ nhật trùng nhau (nói cách khác : dòng 1 và dòng m liền kề
nhau). Một chú kiến bị từ 1 ơ nào đó thuộc cột 1, muốn tới 1 ô thuộc cột n sao cho tổng
các số trên đờng chú kiến đi qua là lớn nhất và phải đi theo nguyên tắc : chỉ đợc sang
cột kề bên phải cùng hàng hoặc chênh lệch 1 hng.

Dữ liệu vào lấy từ file văn bản TSP.INP
dòng đầu là 2 số m,n

m dòng tiếp theo thể hiện bảng số hình chữ nhật (mỗi dòng n số)
Kết qủa ghi ra file văn bản TSP.OUT

dòng đầu là tổng các số mà kiến đi qua

n sè thĨ hiƯn : sè thø i trong n sè này là chỉ số dòng mà kiến đi qua cột i

Bài 3: (Mua vé tàu hoả)

Tuyn ng st t thành phố A đến thành phố B đi qua một số nhà ga. Có thể
biểu diễn các nhà ga nh là các điểm trên một đoạn thẳng AB. Nhà ga tại A có số hiệu 1,
nhà ga tiếp theo là 2,..., nhà ga cuối cùng tại B có số hiệu N. Giá vé đi lại giữa hai nhà
ga nào đó phụ thuộc vào khoảng cách giữa chúng. Cách tính giá vé nh sau : Gọi khoảng
cách giữa hai ga là X

</div>
(47)<div class='page_container' data-page=47>

NÕu L1 < X L2 thì giá vé là C2
Nếu L2 < X L3 thì giá vé lµ C3

Vé đi thẳng từ nhà ga này đến nhà ga khác chỉ có thể đặt mua nếu khoảng cách giữa
chúng khơng vợt q L3. Vì thế nhiều khi để đi từ nhà ga này đến nhà ga khác ta phải
mua một số vé. Ví dụ trên tuyến đờng sắt cho trên hình vẽ sau:

để đi từ ga 2 đến ga 6 khơng thể mua vé đi thẳng. Có nhiều cách đặt mua vé để đi từ nhà
ga 2 đến nhà ga 6. Chẳng hạn, đặt mua vé từ ga 2 đến ga 3 mất chi phí C2 và sau đó mua
vé để đi từ ga 3 đến ga 6 mất chi phí C3 và chi phí tổng cộng để mua vé đi từ ga 2 đến ga
6 theo cách này là C2+C3. Lu ý là mặc dù khoảng cách từ ga 2 đến ga 6 là 2*L2 nhng
không thể đặt mua 2 vé với giá C2 để đi từ ga 2 đến ga 6 với chi phí tổng cộng là 2*C2 vì
mỗi vé chỉ có giá trị đi lại giữa hai nhà ga đó.

u cầu tìm cách đặt mua vé để đi lại giữa hai nhà ga cho trc vi chi phớ mua vộ
nh nht.

Dữ liệu vào từ file văn bản RTICKET.INP

Dũng u tiờn ghi cỏc s nguyên L1,L2,L3,C1,C2,C3 theo đúng thứ tự liệt kê
 Dòng thứ hai là số lợng nhà ga: N

 Dßng thø ba ghi 2 số nguyên là số hiệu hai nhà ga cần mua vé : s và t

N-1 dũng tip theo, mỗi dòng thứ i trong N-1 dòng này ghi số nguyên là khoảng
cách từ nhà ga 1 (tại A) đến nhà ga thứ i+1 (i=1,2,..,N-1)

Dữ liệu ra file RTICKET.OUT chi phí nhỏ nhất tìm đợc.

Hạn chế kỹ thuật : 1  L1 < L2 < L3  109, 1  C1< C2 < C3  109, 2  N  104
Chi phí từ nhà ga đầu tiên A đến nhà ga cuối cùng B không vợt quá 109

VÝ dô:

RTICKET.INP RTICKET.OUT

3 6 8 20 30 40 70

</div>
(48)<div class='page_container' data-page=48>

15
23

Bài 4: (Xếp lịch giảng) Một giáo viên cần giảng N vấn đề đợc đánh số từ 1 đến N
(N<=1000). Mỗi một vấn đề i có thời gian là Ai (i=1... N). Mỗi vấn đề chỉ giảng không
quá 1 buổi. Thời gian tối đa của một buổi là L (L<=500). Vấn đề i phải giảng trớc vấn
đề i+1. Trong một buổi có thể bố trí giảng vài vấn đề, nhng nếu thừa lợng thời gian là t
thì buổi đó đợc đánh giá là lãng phí thời gian với mức d :

0 .. . .. .. . .. .. .t=0
−c.. . .. .. . .. 1≤ t ≤10

t −10¿2. .. ..t>10
¿

¿d={{

trong đó c là hằng số cho trớc.

Hãy xếp lịch dạy trong số buổi ít nhất và tổng các số d nh nht cú th c

Dữ liệu vào từ file văn bản LICH.INP gồm:

Dòng đầu là số N

Dòng tiếp theo là L và C

Dòng cuối cùng là N sè thĨ hiƯn cho A1,A2,....,AN

KÕt qu¶ ghi ra file LICH.OUT gồm

Dòng đầu tiên là số buổi của lịch

Dòng tiếp theo là tổng di nhỏ nhất đạt đợc

VÝ dô :
‘LICH.INP’
10

120 10

80 80 10 50 30 20 40 30 120 100
‘LICH.OUT’

6
2700

Bài 5 :(Xếp hàng mua vé) Có N ngời xếp hàng mua vé. Ta đánh số họ từ 1 đến N theo
thứ tự đứng trong hàng. Thời gian phục vụ bán vé cho ngời thứ i là ti. Mỗi ngời cần mua
1 vé nhng đợc quyền mua tối đa 2 vé vì thế một số ngời có thể nhờ ngời đứng ngay trớc
mình mua hộ. Ngời thứ i nhận mua vé cho ngời thứ i+1 thì thời gian mua vé cho 2 ngời
là ri. Tìm phơng án sao cho N ngời đều có vé với thời gian ít nhất.

</div>
(49)<div class='page_container' data-page=49>

 Dßng thø nhÊt chøa sè N (1<N 2000)

 Dßng thø hai ghi N số nguyên dơng t1,t2,....,tN
Dòng thứ ba ghi N-1 số r1,r2,....,rN-1

Kết quả ghi ra file văn bản TICK.OUT

Dòng thứ nhất ghi tổng thời gian phục vụ bán vé.

Dòng tiếp theo ghi chỉ số của các khách hàng cần rời khỏi hàng (nếu không có ai
cần phải rời khỏi hàng thì quy ớc ghi số 0).

VÝ dô:

TICK.INP
5

2 5 7 8 4
3 9 10 10
TICK.OUT

2 4

TICK.INP
4

7 8 4

4 50 50 50 50
TICK.OUT
24

Bài 6: (Phân tích số). Với x nguyên dơng, gọi f(x,k) là số cách phân tích x thành tổng
các số nguyên tố mà mỗi số nguyên tố có trong tổng không quá k lần.

f(12,6) = 7 vì có 7 cách phân tích :

12=2 + 2 + 2 + 2 + 2 + 2

12=2 + 2 + 2 + 3 + 3
12=2 + 2 + 3 + 5

12=2 + 3 + 7
12=2 + 5 + 5

12=3 + 3 + 3 + 3
12=5 + 7

f(12,3) = 5 vì có 5 cách phân tích :
12=2 + 2 + 2 + 3 + 3
12=2 + 2 + 3 + 5

12=2 + 3 + 7
12=2 + 5 + 5
12=5 + 7

f(12,1) = 2 vì có 2 cách phân tích :
12 =2 + 3 + 7

</div>
(50)<div class='page_container' data-page=50>

Yêu cầu của bài toán là : Cho mảng hai chiều A[1... M,1... N] có M dòng N cột, mỗi
phần tử là số nguyên dơng không quá 100 và cho số nguyên dơng k. HÃy lập mảng hai
chiều B gồm M dòng N cột sao cho B[i,j] = f(A[i,j],k)

Dữ liệu vào lấy từ file văn bản PTS.INP gồm :
Dòng thứ nhất là 3 số M, N, k

M dòng tiếp theo là mảng A[1... M,1... N], mỗi dòng N số, hai số cách nhau ít nhất
một dấu cách

Kết quả ghi ra file PTS.OUT m dòng là mảng B[1... M,1... N], mỗi dòng N số, hai số

cách nhau ít nhất một dấu cách

Hạn chế kỹ thuật : M, N 100

Ví dô :

PTS.INP

2 3 3
1 3 5
7 100 12

PTS.OUT

0 1 2
3 4752 5

Bài 7: (Shopping Offers- IOI’95 - Bài 2 Ngày 1) Trong một cửa hàng, mỗi loại hàng
có một giá. Ví dụ giá một bơng hoa là 2 ICU (ICU - đơn vị tiền) và giá một cái bình là
5 CIU. Để thu hút nhiều khách hàng, cửa hàng đề ra một số cách bán đặc biệt.

Một cách bán đặc biệt liên quan đến việc bán một hay một số mặt hàng với một
giá chung đợc giảm. Ví dụ 3 bơng hoa bán với giá 5 ICU thay vì 6 ICU ; 2 bình và 1
bơng hoa với giá 10 ICU thay vì 12 ICU.

Viết chơng trình tính giá mà một khách hàng trả cho một nhu cầu mua hàng để
tận dụng một cách tối u các cách bán đặc biệt nêu trên - có nghĩa là chi phí thấp nhất có
thể đợc. Ví dụ với các giá và với các cách bán đặc biệt nêu trên, giá thấp nhất để mua đ
-ợc 3 hoa và 2 bình là 14 ICU ; 2 bình và 1 hoa là 10 ICU ; 2 hoa với giá bình thờng là 4
ICU.

</div>
(51)<div class='page_container' data-page=51>

 999). Chú ý rằng trong một u cầu có khơng q 5x5 = 25 đơn vị hàng. Dòng thứ
nhất của file OFFER.TXT chứa số s là số cách bán đặc biệt (0  s  99). Mỗi dịng
trong số s dịng tiếp theo mơ tả một cách bán đặc biệt bằng cách cho cấu trúc và giá đã
đợc giảm của nó. Số đầu tiên n của một dòng nh vậy là số loại hàng trong cách bán đặc
biệt tơng ứng (với dịng đó) (1  n  5) ; n cặp số tiếp theo (c, k) trong đó c là mã loại

hàng, k là số đơn vị loại hàng đó (1  k  5, l  c  999), số p cuối cùng trong dịng là
giá (đã đợc giảm) của lơ hàng này (1  p  9999). Giá đã đợc giảm nhỏ hơn tổng các
giá bình thờng.Dữ liệu ra : Ghi ra file OUTPUT.TXT, một dịng ghi chi phí thấp nhất
phải trả cho nhu cầu mua nêu trong file vào.

INPUT.TXT
2

7 3 2
8 2 5

OFFER.TXT
2

1 7 3 5
2 7 1 8 2 10
OUTPUT.TXT
14

Bài 8: (MÃ vạch)

Cho bé 3 sè
(N,M,K) nguyên

không âm

(N<=100,M,K<=33
). Ngi ta định
nghĩa mỗi bộ 3 số
trên ứng với 1 mã là

một xâu kí tự dạng
nhị phân thoả mãn :
Chứa đúng N chữ
số. Các chữ số 0
liền nhau hoặc các
chữ số 1 liền nhau
gọi là 1 vạch, phải
có đúng M vạch. Số
chữ số trong 1 vạch
gọi là độ rộng của
vạch. Độ rộng tối
đa của vạch là K.
Vạch đầu tiên của
mã phải là vạch
gồm các chữ số 1.
Lập trình thực hiện
các yêu cầu sau :
1) Lấy dữ liệu từ
File ‘MV.INP’ tổ
chức nh sau :

- Dòng đầu
là 3 số N,M,K

- Dòng thứ 2
là số p

- P dòng tiếp
theo : mỗi dòng là

một m· M i (0< i
<P+1) cña bé mÃ
(M,N,K)

2) Thông tin ra gửi
vào File MV.OUT
:

- Dòng đầu
là số nªu tỉng sè
m· cđa bé m·
(N,M,K)

- TiÕp theo
gåm p dßng, mỗi
dòng ghi 1 số là vị
trí của mÃ M i trong
tự điển xếp tăng các
mÃ của bé m·
(N,M,K).

VÝ dô

File ‘MV.INP’
7 4 3

</div>
(52)<div class='page_container' data-page=52>

File MV.OUT
16

3
1
13
16

Bài 9:(Vòng quanh thế giới - Bài 3- Đề thi học sinh giỏi Toàn quèc 13-3-2001)

Trên tuyến đờng của xe du lịch vòng quanh thế giới xuất phát từ bến x có N
khách sạn đánh số từ 1 đến N theo thứ tự xuất hiện trên tuyến đờng, trong đó khách sạn
N là địa điểm cuối cùng của tuyến đờng mà tại đó xe bắt buộc phải dừng. Khách sạn i
cách địa điểm xuất phát A(i) km (i=1,2,.., N): A(1)<A(2)<.. <A(N).

Để đảm bảo sức khoẻ cho hành khách, theo tính tốn của các nhà chuyên môn,
sau khi đã chạy đợc P km xe nên dừng lại cho khách nghỉ ở khách sạn. Vì thế, nếu xe
dừng lại cho khách nghỉ ở khách sạn sau khi đã đi đợc Q km thì lái xe phải tr mt lng
pht l (Q-P)2

Yêu cầu

Hóy xỏc nh xem trờn tuyến đờng đến khách sạn N, xe cần dừng lại nghỉ ở những
khách sạn nào để tổng lợng phạt mà lỏi xe phi tr l nh nht.

Dữ liệu vào từ file văn bản BL3.INP

Dòng đầu tiên chứa số nguyên dơng N (N10000)
Dòng thứ hai chứa số nguyên dơng P (P500)

Dũng th ba cha cỏc s nguyên dơng A(1), A(2),.., A(N) (hai số liên tiếp trên dòng

đợc ghi cách nhau bởi dấu cách) (A(i) 2000000, i=1, 2,..,N)

Kết quả ghi ra file văn bản BL3.OUT

Dòng đầu ghi Z là lợng phạt mà lái xe phải trả

Dòng thứ hai ghi k là tổng số khách sạn mà lái xe cần dừng lại cho khách nghỉ

Dũng thứ ba chứa chỉ số của k khách sạn mà xe dừng cho khách nghỉ (trong đó nhất
thiết bao gồm cả chỉ số của khách sạn thứ N)

VÝ dô
BL3.INP
4

300

250 310 550 590

BL3.OUT
500
2
2 4

Bµi 10:(Little shop of flowers -IOI’99 - Ngµy 1 Bµi 1)

</div>
(53)<div class='page_container' data-page=53>

thành một hàng trên cửa sổ. Các bình hoa đợc gắn cố định và đợc đánh số liên tục từ 1
đến V, trong đó V là số bình, theo thứ tự từ trái qua phải sao cho bình 1 là bên trái nhất
cịn bình V là bên phải nhất. Mỗi bó hoa đợc gán một số nguyên duy nhất có giá trị
trong khoảng 1 và F và có thể cắm vào các bình khác nhau. Số hiệu của các bó hoa có ý

nghĩa nh sau: bó hoa i phải nằm bên trái bó hoa j trong dãy các bình hoa nếu i<j. Ví dụ,
giả sử ta có 1 bó hoa đỗ quyên (có số hiệu là 1), 1 bó hoa thu hải đờng (có số hiệu là 2)
và 1 bó hoa cẩm chớng (có số hiệu là 3). Bây giờ, tất cả các bó hoa phải đợc cắm vào
dãy các bình hoa sao cho bảo đảm ràng buộc về thứ tự các số hiệu. Bó hoa đỗ quyên
phải đợc cắm vào bình phỉa trái của bình hoa thu hải đờng. Còn hoa thu hải đờng phải
đ-ợc cắm vào bình phía bên trái của bình hoa cẩm chớng. Nếu số bình hoa nhiều hơn số
bó hoa thì những bình khơng dùng tới sẽ để trống. Mỗi bình chỉ đợc cắm 1 bó hoa.

Mỗi bình hoa có đặc điểm khác nhau (cũng nh bản thân các bó hoa). Vì vậy, khi
một bó hoa đợc cắm vào bình sẽ có giá trị thẩm mỹ nhất định, đợc biểu diễn bởi 1 số
nguyên. Các giá trị thẩm mỹ đợc cho trong bảng dới đây. Các bình để trống có giá trị
bằng 0.

Hoa

B×nh hoa

1 2 3 4 5

1- Đỗ quyên 7 23 -5 -24 16

2- Thu hải đờng 5 21 -4 10 23

3- CÈm chíng -21 5 -4 -20 20

Theo bảng trên, hoa đỗ quyên sẽ rất hấp dẫn khi đợc cắm vào bình 2, nhng sẽ rất
khó coi khi cắm vào bình 4.

Để nhận đợc hiệu quả thẩm mỹ tốt nhất, bạn phải tìm cách cắm các bó hoa vào
bình tn theo ràng buộc về thứ tự sao cho tổng các giá trị thẩm mỹ là lớn nhất. Nếu có

nhiều cách cắm có cùng giá trị thẩm mỹ thì chỉ cần nêu một trong những cách cắm (và
chỉ nêu đúng một cách mà thơi).

Gi¶ thiÕt

 1 F  100 trong đó F là số bó hoa. Các bó hoa đợc đánh số từ 1 đến F

 F  V  100 trong đó V là số bình hoa. Các bình hoa đợc đánh số từ 1 đến V. Bình hoa
1 đợc đặt trái nhất, bình hoa V đợc đặt phải nhất.

 -50  Aij  50 trong đó Aij là giá trị thẩm mỹ đạt đợc khi cm bú hoa i vo bỡnh j.

Dữ liệu vào

D liệu vào đợc cho trong file văn bản có tên flower.inp, có cấu trúc nh sau:
 Dịng đầu tiên chứa 2 số F, V

</div>
(54)<div class='page_container' data-page=54>

D÷ liƯu ra

Dữ liệu đợc đa ra file văn bản có tên là flower.out chứa 2 dòng:
 Dòng đầu tiên chứa giá trị tổng nhận đợc theo cách cắm của bạn

 Dòng thứ hai biểu diễn cách cắm nh là danh sách F số, sao cho số thứ k trong dịng này
cho biết bình hoa dùng để cắm bó hoa có số hiệu k.

VÝ dô

Flower.inp
3 5

7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
Flower.out

53
2 4 5

2. H íng dÉn:

Bµi 2: (KiÕn leo quanh ống trụ)

Thêm dòng 0 có giá trị nh dòng m và dòng m+1 nh dòng 1. Bài giải giống bài
mẫu Di chuyển từ Tây sang Đông với lu ý khi kiến bò vào một ô thuộc dòng m+1
thì nhấc nó chuyển về ô thuộc dòng 1 cùng cột, khi kiến bò vào một ô thuộc dòng 0
thì nhấc nó chuyển về ô thuộc dòng m cùng cột. Nói cách khác cần thực hiện tổ chức
mảng vòng.

Bài 3: (Mua vé tàu hoả)

Mảng D(N) ghi khoảng cách các nhà ga: D[i] là khoảng cách từ nhà ga i tới nhà
ga A (số hiệu 1)

Dùng mảng nhÃn NH và thực hiện phơng pháp gán nhÃn cụ thể nh sau:

Khởi trị: NH[i] := Maxlongint;

Söa nh·n:i: s i  t-1 ; j: i+1 j  t

NH[j] = Min {NH[j], NH[i] + C[p] } trong đó p là 1,2,3 tơng ứng với D[j]-D[i] thuộc

(0,L1], (L1,L2], (L2,L3].

Lu ý: Li, Ci thuộc [1,109] nên phần tử của mảng NH và mảng D có thể sẽ nhận

giỏ tr lớn vậy khai báo kiểu phần tử của chúng là real. Song số phần tử của 2 mảng là
104 nên ít nhất một mảng phải khai báo kiểu con trỏ. Tuy nhiên cũng cần l u ý thêm khi
ghi tổng chi phí vào file output phải đúng ghi dạng số nguyên.

</div>
(55)<div class='page_container' data-page=55>

Gợi ý: Do điều kiện: bài giảng i phải giảng trớc bài giảng i+1 nên số buổi ít nhất
hồn thành n bài giảng sẽ tìm đợc bằng cách xếp lần lợt các bài giảng từ bài 1 cho đến
N sao cho trong mỗi buổi số bài giảng là tối đa.

Sau đó ta có thể điều chỉnh bài giảng cuối cùng của mỗi buổi thành bài giảng đầu
tiên của buổi kế tiếp theo thuật toán quy hoạch động nh sau:

a) Tỉ chøc d÷ liƯu:

Mảng s(N): s[i] là số buổi tính từ bài giảng i đến bài giảng N.

Mảng w(N): w[i] cho giá trị của lợng đánh giá thời gian lãng phí ít nhất tính từ
bài giảng i đến bài giảng N.

b) Thùc hiƯn tht to¸n:

Bớc 1: Tính giá trị các phần tử của mảng s: để tính s[i] ta xếp lần lợt các bài giảng từ bài
i cho đến N sao cho trong mỗi buổi số bài giảng là tối đa (nghĩa là còn xếp đợc thỡ c
xp).

Bớc 2: Tính giá trị các phần tử của mảng w: Xây dựng w[i] nh sau:

T bi ging i ta bắt đầu xếp lại các buổi giảng sau đó bằng cách cho các bài từ i liên
tiếp đến bài j vào một buổi nếu thoả mãn hai điều kiện sau:

 s[i]=s[j+1]+1 (nghĩa là bảo đảm số buổi không tăng so với cách xếp ban đầu, vì cách
xếp ban đầu là tối u về số buổi)

 sau bài j, buổi mới tạo ra còn thừa lợng thời gian t sao cho lợng đánh giá lãng phí
thời gian của nó cộng với tổng đánh giá thời gian lãng phí từ bài giảng j+1 đến N phải
nhỏ hơn tổng đánh giá thời gian lãng phí từ bài giảng i đến bài giảng N.

Lu ý: Dùng thêm biến toàn cục là mảng d(N): d[i] để đánh dấu đã xếp tối u từ bài giảng

i đến N hay cha.

Bµi 5:

Xây dựng mảng nhãn L(N) với ý nghĩa: L[k] là số thời gian ít nhất để phục vụ vé
cho k ngời (từ 1 đến k). Rõ ràng nếu ngời k tự mua vé thì thời gian ít nhất phục vụ k
ng-ời là t[k]+L[k-1], nếu ngng-ời k nhờ ngng-ời k-1 (xếp hàng trên mình) mua hộ thì thng-ời gian ít
nhất phục vụ k ngời là r[k-1]+ L[k-2]. Vậy thời gian ít nhất để phục vụ xong k ngời là:

L[k] := Min { t[k]+L[k-1], r[k-1]+ L[k-2] }

Sau khi xây dựng xong mảng L, dựa vào 3 mảng L, T, R ta tìm ra kết quả những
ngời nào cần mua vé ghi vào mảng kết quả KQ theo nhËn xÐt:

NÕu t[k]+L[k-1]  r[k-1]+ L[k-2] th× ngêi k mua nên ghi KQ[k]:=1 ngợc lại thì
ngời k-1 mua nªn ghi kq[k-1]:=1.

</div>
(56)<div class='page_container' data-page=56>

Dùng mảng A chứa 25 số nguyên tố đầu tiên, mảng L(100,25) là mảng nhãn với ý

nghĩa: L[x,k] là số cách phân tích số x (x100) nếu số nguyên tố A[k] là số hạng duy
nhất đợc lặp lại w lần. Để xây dựng mảng L, có thể dùng hàm đệ quy sau:

function qhd(x,k:integer):longint;
var sum :longint;

dem :byte;
y :integer;
begin

y:=x;

if L[y,k]=-1 then
begin

sum := 0;

dem := w {w là số lần tối đa của 1 số hạng duy nhất đợc lặp lại}
while (x>=A[k])and(dem>0) do

begin

dec(dem);
x:=x-A[k];

sum:=sum+qhd(x,k-1);{cách có chứa A[k] với số lần = w-dem}
end;

sum:=sum+qhd(y,k-1);{cách không chứa A[k]}
L[y,k]:=sum;

end;

qhd:=L[y,k];
end;

Bµi 7: (Shopping Offers - IOI’95- Ngµy1 Bµi 2)

</div>
(57)<div class='page_container' data-page=57>

 Xây dựng bảng giá bán cho mọi lô hàng gồm 5 loại hàng (theo thứ tự 1,2,3,4,5) có
số lợng tơng ứng là i,j,u,h,r:

+ Bớc 1: L[i,j,u,h,r]:= p[1]*i+p[2]*j+p[3]*u+p[4]*h+p[5]*r;

+ Bc 2: Tại những điểm (i,j,u,h,r) là một lô hàng bán đặc biệt thì sửa lại bảng giá tại
điểm này theo cách bỏn c bit.

Tạo bảng nhÃn cho biết giá mua rẻ nhất của mỗi lô hàng theo công thức:

L[i,j,u,h,r]=

1ms

Min

{L[i,j,u,h,r],L[d[m,1],d[m,2],d[m,3],d[m,4],d[m,5]]+

L[i-d[m,1],j-d[m,2],u-d[m,3],h-d[m,4],r-d[m,5]])}

(i,j,u,h,r): 1ik[1],1jk[2],1uk[3],1hk[4],1rk[5]

Bài 8:(MÃ vạch)

Xây dựng mảng hai chiều L(N,M) với ý nghĩa L[i,j] là số lợng mÃ có i chữ số và
j vạch (mỗi vạch là 1 nhóm chữ 1 hoặc 0 liên tục).

Khi tr: Khi mã chỉ có 1 vạch thì rõ ràng với mọi mã có số chữ số từ 1 đến k (số

chữ tối đa trong một vạch) đều duy nhất nên L[i,1]=1, 1 i  k.

Khi m· cã sè chữ số bằng số vạch thì mÃ duy nhất nên L[i,i]=1, 1 i m.

Xây dựng tiếp các phần tử khác của mảng L dựa vào công thức:

i: 2 i  n, j: 2 j  min(i,m) - ở đây min(i,m) là số vạch có thể tạo khi số chữ
của mÃ là i.

L[i,j] =

L[i-h,j-1]
1h  min(k,i-j+1)

Sở dĩ có cơng thức này vì: Mỗi mã x có i chữ và j vạch có thể tạo ra bằng cách
lấy tất cả các mã y có số vạch nhỏ hơn 1 vạch bổ xung thêm một số chữ số 0 hoặc 1 vào
bên phải sao cho tổng số chữ đủ i chữ. Rõ ràng, những mã y nh thế có số chữ ít hơn số
chữ của x là h chữ (1hmin(k,i-j+1))

VÝ dô: N=7; M=4; K=3

L[7,4]=L[6,3]+L[5,3]+L[4,3]
L[6,3]=L[5,2]+L[4,2]+L[3,2]
L[5,3]=L[4,2]+L[3,2]+L[2,2]
L[4,3]=L[3,2]+L[2,2]

L[5,2]=L[3,1]+L[2,1]

</div>
(58)<div class='page_container' data-page=58>

Do: L[1,1]=L[2,1]=L[3,1]=1, L[1,1]=L[2,2]=L[3,3]=L[4,4]=1 nên có thể tính đợc
L[7,4]=16

X©y dùng xong mảng L(n,m) thì phần tử L[n,m] chính là số lợng các mÃ có n
chữ số và m vạch.

Nhim v th hai của bài toán là từ mã cho trớc hãy tìm vị trí của nó trong tự
điển xếp tăng xâu nhị phân biểu diễn mã đó: Giả sử sau khi đọc đ ợc một mã x từ file
input ta chứa nó trong mảng một chiều A(n). Tiếp theo từ mảng A(n) tạo mảng B(m)
gồm m phần tử, mỗi phần tử là độ rộng của một vạch. Vị trí của mã x là số lợng các mã
nhỏ hơn nó cộng thêm 1. Để tìm số lợng các mã nhỏ hơn mã x ta dựa vào mảng B(m) và
mảng L(n,m).

Cụ thể: ta giữ lại phần đầu của mã, thay phần sau bởi mã nhỏ hơn có cùng chữ số
với phần sau. Phần đầu của mã cho rộng dần đi từ vạch 1 đến vạch m-1. Khi phần đầu
rộng là j có chữ số cuối cùng thuộc vạch thứ i gồm các số 1 là vạch  thì ta cho j chạy từ
chữ số đầu tiên của vạch này đến chữ số sát cuối cùng của vạch này. Với mỗi vị trí của j
ta thay phần còn lại của mã (n-j chữ số) bởi các mã có số chữ là n-j với số vạch là m-i sẽ
đợc các mã nhỏ hơn x có n chữ số và m vạch, số lợng các mã này là

Sl1=

L[n-j,m-i] (t1+1 là vị trí đầu, t1+B[i]-1 là vị trí sát cuối của )

t1+1j t1+B[i]-1

còn trong trờng hợp khi vạch  gồm các số 0 thì ta tạo ra các mã nhỏ hơn bằng cách
cho j chạy qua vạch , bắt đầu vào vạch tiếp theo là vạch , sau đó cho j chạy từ vị trí
thứ nhất của vạch  cho đến k-1, với mỗi vị trí của j ta ghép phần đầu của mã (từ 1 đến
j) với phần cịn lại là mã có số chữ là n-j-1, số vạch là m-i sẽ tạo thành mã nhỏ hơn, số
lợng các mã này là

Sl2=



L[n-j-1,m-i]
t1+B[i]j t1+k-1

VËy vị trí của mÃ x là sl1+sl2+1.

Bài 9: (Vòng quanh thÕ giíi - §Ị thi häc sinh giái qc gia 2001- Bµi 1)

Nếu khơng kể trờng hợp xe có thể đi trở lại thì bài tốn có thể giải bằng quy
hoch ng:

Xây dựng mảng nhÃn L(N) với ý nghĩa L[i] là giá tiền phạt ít nhất khi đi tới
thành phố có số hiệu là i.

Khởi trị: L[1]=(A[1]-P)2

Xây dựng tiếp: L[i] = Min {L[i], L[j]+(A[i]-A[j]-P)2}

1  j  i-1

</div>
(59)<div class='page_container' data-page=59>

A[i]-A[j]-P>0 , do đó phải thoả mãn điều kiện cần cho tìm kiếm tiếp là:(A[i]-A[j]-P)2 không
lớn hơn giá trị lu min tốt nhất trong thời điểm đang tìm kiếm.

Điều lu ý thứ hai: Giá trị (A[i]-A[j]-P)2 có thể vợt qua maxlongint, nên mảng
nhãn L có các phần tử kiểu comp. Lệnh sau có thể mắc lỗi: x:=y*y; (trong đó x kiểu
comp, y kiểu longint). Có thể sửa lại là: x:= y*1.0*y; hoặc x := y; x := x*x;

Bµi 10:(Little shop of flowers -IOI’99 Ngµy 1 Bµi 1)

Cách 1: áp dụng nguyên lý tối u của Bellman: Xây dựng hàm đệ quy QHD(i,j)

cho tổng giá trị thẩm mỹ tốt nhất khi chỉ xét cắm các bó hoa từ i đến M, và các bình hoa
chỉ có từ bình j tới N. Đồng thời xây dựng mảng nhãn 2 chiều L(M,N) với ý nghĩa L[i,j]
lu lại tổng giá trị thẩm mỹ tốt nhất khi chỉ xét cắm các bó hoa từ i đến M, và các bình

hoa chỉ có từ bình j tới N. Bó hoa i sẽ cắm vào bình có số hiệu k (jk N-M+i). Vậy:

L[i,j] := Max {A[i,k] + QHD(i+1,k+1}}
j  k N-M+i

Dùng thêm mảng S(M,N) để ghi nhận quá trình cắm: S[i,j] là số hiệu bình cắm bó hoa i
(khi bó hoa i có thể cắm vào bình có số hiệu từ j đến N-M+i).

C¸ch 2:

a) Lập hệ thức:

Gọi S[i,j] là tổng giá trị thẩm mỹ khi cắm i bó hoa (1...i) vào j bình (1...j):

+ Nếu i=j có 1 cách cắm duy nhất: bó hoa có số hiệu nào cắm vào bình có sè hiÖu Êy

S[j,j] :=  A[i,i] (i=1,2,...j)

+ Nếu i<j thì bình j có thể đợc cắm bơng hoa cuối cùng (bó hoa i) hoặc khơng. Nếu bó
hoa i cắm bình j thì S[i,j] := S[i-1,j-1] + A[i,j], nếu khơng S[i,j] := S[i,j-1]. Do đó

S[i,j] = Max { S[i-1,j-1] + A[i,j] , S[i,j-1]} (*)

b) Tổ chức dữ liệu ban đầu:

Mng hai chiều A, S có phần tử kiểu nguyên. Mảng hai chiều D có mỗi phần tử D[i,j] là
mảng một chiều đánh dấu các bình có cắm hoa khi có i hoa, j bình (vậy coi nh D là
mảng ba chiều kích thớc q lớn khơng thể chấp nhận đợc)

Xây dựng S: Khởi trị cột 0 bằng 0, xây dựng dần các cột từ 1 đến V, trong mỗi cột xây

dựng S[j, j] trớc, sau đó tìm dần các phần tử từ dới lên theo công thức (*). Trong bảng
d-ới đây dấu X là giá trị đã tính

0 0 0 0 0 0 0 0 0 0

0 X X X X X X

0 X X X X X

0 X X X [i-1,j-1]

0 X X [i,j-1] [i,j]

0 X X X

0 X X

0 X

Trong quá trình xây dựng mảng S thì cũng xây dựng mảng D:

Nu S[i,j] = S[i-1,j-1] + A[i,j] (nghĩa là có cắm bó hoa i vào bình j) thì trong mảng D[i,j] phải
đánh dấu phần tử j (bằng 1 chẳng hạn)

c) Cải tiến làm chơng trình đợc thực hiện tốt hơn:

</div>
(60)<div class='page_container' data-page=60>

Chỉ dùng mảng một chiều T coi nh một cột của S thay đổi dần từ cột 1 đến cột V và trong
mỗi cột j ta cũng chỉ cần xây dựng t dũng j n dũng 1.

Đồng thời dùng mảng hai chiỊu C thay cho m¶ng ba chiỊu D: C[i] cho biết một phơng án

tối u cắm i bó hoa . C[i,j]=1 là bình j có cắm hoa (trong bài toán cắm i bó hoa vào j bình)

Mng C có thể cải tiến tốt hơn nữa vì phần tử của nó chỉ nhận giá trị 0 và 1 nên có thể
dùng kỹ thuật quản lý bít để tiết kiệm miền nhớ. Chiều thứ hai của C chỉ cần 16 phần tử, mỗi
phần tử kiểu byte. Vậy có 16 x8 = 120 bít, có thể đánh dấu tới 120 bình hoa.

3 - Ch ơng trình:

Bài 2: (Kiến leo quanh ống trô)

uses crt;

const maxm = 11;
maxn = 101;

fi = 'TSP.INP';
fo = 'TSP.OUT';

m1 = array[1..maxn] of extended;

var a,L : array[0..maxm] of m1;
m,n : byte;

f,g : text;
procedure input;

var i,j :byte;
begin

readln(f,m,n);

for i:=1 to m do
begin

for j:=1 to n do read(f,a[i,j]);
readln(f);

end;
a[0]:=a[m];
a[m+1]:=a[1];
for i:=0 to m+1 do

for j:=1 to n do l[i,j]:=maxlongint;
end;

function minso(u,v,t:extended):extended;
begin

</div>
(61)<div class='page_container' data-page=61>

if u>t then u:=t;
minso:=u;

end;

procedure solution;
var i,j :byte;
k :byte;
begin

for k:=0 to m+1 do l[k,1]:=a[k,1];
for j:=2 to n do

begin

for i:=1 to m do

l[i,j]:=minso(l[i-1,j-1],l[i,j-1],l[i+1,j-1])+a[i,j];
l[0,j]:=l[m,j];

l[m+1,j]:=l[1,j];
end;

end;

procedure output;
var i,j,k,lk : byte;
mx : extended;

q : array[1..maxn]of byte;
begin

mx:=maxlongint;
for k:=1 to m do
if l[k,n]<mx then
begin

mx:=l[k,n];
lk:=k;
end;
i:=lk;
j:=n;

while j>0 do
begin

q[j]:=i;

</div>
(62)<div class='page_container' data-page=62>

if l[i-1,j-1]+a[i,j]=l[i,j] then
begin

i:=i-1;

if (i=0) and (l[i+1,j-1]+a[i,j]=l[i,j])
then i:=i+2;

if i=0 then i:=m;
end

else if l[i+1,j-1]+a[i,j]=l[i,j] then
begin

inc(i);

if i=m+1 then i:=1;
end;

dec(j);
end;

for k:=1 to n do write(g,q[k],#32);
writeln(g,#10,#13,mx:0:0);

end;
BEGIN

assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
repeat
input;
solution;
output;

until seekeof(f);
close(g); close(f);
END.

Bài 3:(Mua vé tàu hoả)

uses crt;

const max = 10001;

</div>
(63)<div class='page_container' data-page=63>

fo = 'RTICKET.OUT';

type mg = array[0..max] of real;
var l,c : array[1..3] of longint;
nh : mg;

d : ^mg;

s,t,n,coc : longint;
procedure docf;

var f : text;
i : longint;
begin

assign(f,fi);
reset(f);
new(d);

fillchar(d^,sizeof(d^),0);

readln(f,L[1],L[2],L[3],c[1],c[2],c[3]);
readln(f,n);

readln(f,s,t);
if s>t then
begin

coc := s;
s := t;
t := coc;
end;

for i := 2 to t do
readln(f,d^[i]);
close(f);

end;

procedure lam;

var i,j,p : longint;
kc : real;
f : text;
begin

</div>
(64)<div class='page_container' data-page=64>

for i := s to t-1 do
begin

for j := i+1 to t do
begin

kc := d^[j]-d^[i];

if kc > l[3] then break;

if kc <= l[1] then p := 1 else
if kc <= l[2] then p := 2
else p := 3;

if nh[j] > nh[i] + c[p] then
nh[j] := nh[i] + c[p];
end;

end;
assign(f,fo);
rewrite(f);

write(f,nh[t]:0:0);
close(f);

end;
BEGIN
docf;
lam;

dispose(d);
END.

Bµi 4: (Xếp lịch giảng)

uses crt;

const max = 1000;

fi = 'input.txt';
fo = 'output.txt';

</div>
(65)<div class='page_container' data-page=65>

procedure input;
var f : text;
k : integer;
begin

assign(f,fi);
reset(f);
readln(f,n);
readln(f,l,c);

for k:=1 to n do read(f,a[k]);
close(f);

end;

function solution(k:integer):integer;
var t,sb : integer;

begin
sb:=0;

while k<=n do
begin

t:=l;

while (k<=n)and(t>=a[k]) do
begin

t:=t-a[k];
inc(k);
end;
inc(sb);
end;

solution:=sb;
end;

procedure init;
var k : integer;

begin

fillchar(d,sizeof(d),0);
fillchar(w,sizeof(w),0);
d[n+1]:=1;w[n+1]:=0;
fillchar(s,sizeof(s),0);

</div>
(66)<div class='page_container' data-page=66>

end;

function qhd(i:integer):longint;
var j,t : integer;

s1,s2 : longint;
begin

if d[i]=0 then
begin

j:=i;
t:=l;

s1:=maxlongint;

while (j <= n) and (t >= a[j]) do
begin

t:=t-a[j];

if s[i] = s[j+1] + 1 then
begin

if (t<=10)and(t>0) then s2:=-c+qhd(j+1)
else if t>10 then

s2:=(t-10)*(t-10)+qhd(j+1)
else if t=0 then s2:=qhd(j+1);
if s2<s1 then s1:=s2;

end;
inc(j);
end;
d[i]:=1;
w[i]:=s1;
end;

qhd:=w[i];
end;

procedure output;
var f : text;
begin

assign(f,fo);
rewrite(f);

</div>
(67)<div class='page_container' data-page=67>

close(f);
end;

BEGIN
input;

init;
output;
END.

Bµi 5:(XÕp hµng mua vÐ)

uses crt;

const fi = 'tick.inp';
fo = 'tick.out';
max = 5001;

type km1 = array[0..max]of integer;
ktt = array[0..max]of longint;
var

t,r,kq : km1;
L : ktt;
n : integer;
f : text;
procedure read_in;

var i,j :integer;
begin

assign(f,fi);
reset(f);

readln(f,n);

for i:=1 to n do read(f,t[i]); readln(f);
for i:=1 to n-1 do read(f,r[i]);

close(f);
end;

function min(x,y:longint):longint;
begin

</div>
(68)<div class='page_container' data-page=68>

end;

procedure try(k:integer);
begin

if k>n then exit else
begin

L[k]:=min((t[k]+L[k-1]),(r[k-1]+L[k-2]));
try(k+1);

end;
end;

procedure tim_kq(k:integer);
begin

if k<=1 then
begin

kq[k]:=1;

exit;
end;

if (t[k]+L[k-1])<=(r[k-1]+L[k-2]) then
begin

kq[k]:=1; tim_kq(k-1);
end else

begin

kq[k-1]:=1;
tim_kq(k-2);
end;

end;

procedure result;
var i,j :integer;
begin

L[1]:=t[1];
try(2);
tim_kq(n);
end;

</div>
(69)<div class='page_container' data-page=69>

begin

ok:=false;
assign(f,fo);

rewrite(f);

writeln(f,L[n]);
for i:=1 to n do
if kq[i]=0 then
begin

ok:=true;
write(f,i:4);
end;

if not ok then writeln(f,0);
close(f);

end;
BEGIN

read_in;
result;
write_out;
END.

Bài 6: (Phân tích số)

uses crt;

const max = 100;

fi = 'bai1.in2';

fo = 'pts.out';{bai1.ou2}

A : array[1..25] ofbyte=(2,3,5,7,11,13,17,19,23,29,

31,37,41,43,47,53,59,61,67,71, 73,79,83,89,97);

var L :array[0..max,0..max]of longint;

m,n,w,i,j,x :integer;

f,g :text;

function qhd(x,k:integer):longint;
var sum :longint;

</div>
(70)<div class='page_container' data-page=70>

y :integer;
begin

y:=x;

if L[y,k]=-1 then
begin

sum:=0;
dem:=w;

while (x>=A[k])and(dem>0) do
begin

dec(dem);

x:=x-A[k];

sum:=sum+qhd(x,k-1);
end;

sum:=sum+qhd(y,k-1);
L[y,k]:=sum;

end;

qhd:=L[y,k];
end;

BEGIN

for i:=0 to max do

for j:=0 to max do L[i,j]:=-1;
for j:=0 to max do

begin

L[0,j]:=1;
L[j,0]:=0;
end;

L[0,0]:=1;

assign(f,fi);reset(f);
assign(g,fo);rewrite(g);

readln(f,m,n,w);

for i:=1 to m do
begin

</div>
(71)<div class='page_container' data-page=71>

read(f,x);

write(g,qhd(x,25),#32);
end;

writeln(g);
end;

close(f);close(g);
END.

Bài 7:(Cửa hàng bán hoa)

uses crt;

const fi1 = 'input_a.txt';
fi2 = 'offera.txt';
fo = 'output_a.txt';

type mn = array [0..5,0..5,0..5,0..5,0..5] of integer;
nn = array [0..5] of byte;

var l,f : mn; {l:bảng giá bán, f: nhãn cho giá trị giá mua tốt nhất}
c : array [0..6] of integer; {mã hàng mua}
k : array [0..6] of byte; {số đơn vị hàng mua}

p : array [0..6] of integer; {giá bình thờng 1 đơn vị hàng}

t : array [0..999] of byte;{thứ tự của các loại hàng có trong cửa hàng}
d : array [0..100] of nn; {lu cách bán đặc biệt}

s,b : integer; {s: số cách bán đặc biệt, b: số loại hàng cần mua}
procedure read_input;

var i,j,u,h,r : integer;
ff : text;

begin

fillchar(t,sizeof(t),0);
fillchar(p,sizeof(p),0);
fillchar(k,sizeof(k),0);
assign(ff,fi1);

reset(ff);
readln(ff,b);
for i:=1 to b do

begin

</div>
(72)<div class='page_container' data-page=72>

t[c[i]]:=i;
end;

for i:=0 to 5 do
for j:=0 to 5 do

for u:=0 to 5 do
for h:=0 to 5 do
for r:=0 to 5 do

l[i,j,u,h,r]:=p[1]*i+p[2]*j+p[3]*u+p[4]*h+p[5]*r;;
close(ff);

end;

procedure read_offer;

var i,j,n,u,v : integer;

sl : m2;

f : text;

begin

assign(f,fi2);
reset(f);
readln(f,s);
for i:=1 to s do
begin

read(f,n);

fillchar(sl,sizeof(sl),0);
for j:=1 to n do

begin

read(f,u,v);
sl[t[u]]:=v;
end;

readln(f,u);

if l[sl[1],sl[2],sl[3],sl[4],sl[5]]>u then
l[sl[1],sl[2],sl[3],sl[4],sl[5]]:=u;
d[i]:=sl;

end;
close(f);
end;

</div>
(73)<div class='page_container' data-page=73>

begin

thoaman:=true;

if (i1-d[i,1]<0) or (i2-d[i,2]<0) or (i3-d[i,3]<0)
or (i4-d[i,4]<0) or (i5-d[i,5]<0) then thoaman:=false;
end;

function minab(a,b : integer) : integer;
begin

if a>b then a:=b;
minab := a;
end;

function qh(i1,i2,i3,i4,i5 : byte) : integer;
var i : byte;

min : integer;
begin

min:= l[i1,i2,i3,i4,i5];
for i:=1 to s do

if thoaman(i,i1,i2,i3,i4,i5) then
begin

min:=minab(min,l[d[i,1],d[i,2],d[i,3],d[i,4],d[i,5]]+
l[i1-d[i,1],i2-d[i,2],i3-d[i,3],i4-d[i,4],i5-d[i,5]]);
end;

qh:=min;

l[i1,i2,i3,i4,i5]:= min;
end;

procedure tao_nhan;

var i,j,u,h,r: integer;
begin

l[0,0,0,0,0]:=0;

for i:=0 to k[1] do

for j:=0 to k[2] do
for u:=0 to k[3] do
for h:=0 to k[4] do
for r:=0 to k[5] do

</div>
(74)<div class='page_container' data-page=74>

procedure ghi_file;
var g : text;
begin

assign(g,fo);
rewrite(g);

writeln(g,l[k[1],k[2],k[3],k[4],k[5]]);
close(g);

end;
BEGIN

read_input;
read_offer;
tao_nhan;
ghi_file;
END.

Bài 8:(MÃ vạch)

const fi = 'MAVACH.inp';
fo = 'mv.out';
maxn = 101;
maxm = 34;

type mang1 = array[0..maxn,0..maxm] of comp;
mang2 = array[0..maxn] of integer;
var f,g : text;

n,m,k : integer;
L : mang1;
a,b : mang2;
procedure khoi_tri;
var i : integer;
begin

</div>
(75)<div class='page_container' data-page=75>

function min(a,b : integer): integer;
begin

if a < b then min:=a else min:=b;
end;

procedure tao_L;

var i,j,j2 : integer;
sum : comp;
begin

for i:=2 to n do

for j:=2 to min(i,m) do
begin

sum:=0;

for j2:=1 to k do
if (j2<=i) then

sum:=sum+L[i-j2,j-1];
L[i,j]:=sum;

end;

writeln(f,L[n,m]:0:0);
end;

procedure chuyen(a : mang2;var b : mang2);
var i,dem1,dem2 : integer;

begin

dem1 := 0;
a[0] := a[1];
dem2 := 0;

for i:=1 to n do
begin

if a[i] <> a[i-1] then
begin

inc(dem1);

b[dem1] := dem2;

dem2 :=1;
end

</div>
(76)<div class='page_container' data-page=76>

b[m] := dem2;
end;

procedure xuly;

var i,t1,t2,j,j2 : integer;
pos : comp;
begin

chuyen(a,b);
t1:=0;

t2:=m;
pos:=1;

for i:=1 to m-1 do
begin

dec(t2);

if odd(i) then
begin

for j := t1 + 1 to t1 + b[i] - 1 do
pos := pos + L[n-j,t2];

end

else
begin

for j:=t1+b[i] to t1+k-1 do
pos:=pos + L[n-j-1,t2];
end;

t1:=t1+b[i];
end;

writeln(f,pos:0:0);
end;

procedure thuc_hien;

var i,sl,j : integer;
ch : char;
begin

tao_L;

</div>
(77)<div class='page_container' data-page=77>

for j:=1 to n do
begin

read(g,ch);

a[j]:=ord(ch)-48;
end;

readln(g);

xuly;
end;
end;
BEGIN

assign(g,fi);
reset(g);

readln(g,n,m,k);
khoi_tri;

assign(f,fo);
rewrite(f);
thuc_hien;
close(g);
close(f);
END.

Bài 9:(Vòng quanh thế giới)

uses crt;

const fi = 'Bl3.inp';
fo = 'Bl3.out';
max = 10001;

type mang = array[1..max] of longint;
pt = comp;

mang1 = array[1..max] of ^pt;

mang2 = array[1..max] of integer;
var f : text;

</div>
(78)<div class='page_container' data-page=78>

n,p,sl : longint;
z : comp;
procedure docf;

var i : longint;
begin

assign(f,fi);
reset(f);
readln(f,n);
readln(f,p);

for i:=1 to n do read(f,a[i]);
close(F);

end;
procedure khoitri;

var i : longint;
begin

new(nh);

for i:=1 to n do
begin

new(nh^[i]);

nh^[i]^:=0;
end;

nh^[1]^:=(a[1]-p)*1.0*(a[1]-p);
fillchar(tr,sizeof(tr),0);
end;

function timmin(x : longint;Var y : longint):comp;
var min,pu,m2 : comp;

d,i,li,lj : longint;
begin

min:= (a[x]-p)*1.0*(a[x]-p);
li:=0; m2:=0;

for i:=x-1 downto 1 do
begin

</div>
(79)<div class='page_container' data-page=79>

pu:= nh^[i]^ + m2;
if pu<min then
begin

min:=pu;
li:=i;
end;

end;

timmin:=min;

y:=li;

end;
procedure xuli;

var i,j : longint;
begin

khoitri;

for i:=2 to n do
begin

nh^[i]^:=timmin(i,j);
tr[i]:=j;

end;

z:=nh^[n]^;
end;

procedure ghifile;

var i,j,pu : longint;
begin

assign(f,fo);
rewrite(f);

writeln(f,z:0:0);

pu:=n;

sl:=0;
new(kq);
repeat

</div>
(80)<div class='page_container' data-page=80>

pu:=tr[pu];
until pu=0;

writeln(f,sl);

for i:=sl downto 1 do
write(f,kq^[i],' ');
close(F);

end;
BEGIN

clrscr;
docf;
xuli;
ghifile;
END.

Bµi 10:(Little shop of flowers -IOI’99 - Ngµy 1 Bµi 1)

Cách 1: Ta xây dựng trực tiếp mảng L bằng cách xây dựng dòng m trớc, sau đó xây
dựng dần các dịng m-1, m-2,.. cho n dũng 1.

ý nghĩa của mảng L là : L[i,j] thể hiện kết quả tối u của bài toán con: chØ xÐt c¾m

các bó hoa có chỉ số từ i tới M và các bình chỉ có chỉ số từ j đến N. Do quy định về cách
cắm hoa nên việc cắm hoa tối u cho những bó hoa cịn lại vào các bình cịn lạị là quyết
định tối u cho bài tốn cắm tồn bộ hoa với lựa chọn trên tồn bộ bình (theo ngun lý
tối u của Bellman).

uses crt;

const max = 100;

fi = 'flower.inp';
fo = 'flower.out';

var a,L : array[1..max+1,1..max+1] of integer;
s : array[1..max+1,1..max+1] of byte;
m,n : byte;

procedure init;
var i,j : byte;
begin

for i:=1 to m do

</div>
(81)<div class='page_container' data-page=81>

fillchar(s,sizeof(s),0);
end;

procedure input;

var f : text;

i,j : byte;
begin

assign(f,fi);
reset(f);
readln(f,m,n);
for i:=1 to m do

for j:=1 to n do read(f,a[i,j]);
close(f);

end;
procedure qhd;

var p,lp : integer;
k,lk,i,j : byte;
begin

{Xây dựng dòng m cho mảng nhãn L: chỉ có 1 loại hoa m, có các bình k từ j đến N, j=1..N)
for j:=1 to n do

begin

lp := -Maxint;
for k:=j to n do

if lp<A[m,k] then lp := A[m,k];
L[m,j] := lp;

end;

{Xây dựng các dòng tiÕp theo cho m¶ng nh·n L}
for i:=m-1 downto 1 do
for j:=n downto 1 do
if L[i,j]=-5001 then
begin

lp := -maxint;

</div>
(82)<div class='page_container' data-page=82>

begin

p := a[i,k] + L[i+1,k+1];
if p > lp then

begin

lp := p;
lk := k;
end;

end;

L[i,j] := lp;
s[i,j] := lk;
end;

end;

procedure output;
var f :text;

procedure try(i,j:byte);

begin

if s[i,j]>0 then
begin

write(f,s[i,j],#32);
try(i+1,s[i,j]+1);
end;

end;
begin

assign(f,fo);
rewrite(f);
qhd;

writeln(f,L[1,1]);
try(1,1);

close(f);
end;

BEGIN

</div>
(83)<div class='page_container' data-page=83>

C¸ch 2:

uses crt;

const fi = 'flower.in3';
fo = 'camhoa.out';
mn = 100;

var a : array[0..mn,0..mn] of -50..50;
t : array[0..mn] of integer;

c : array[0..mn,0..mn] of 0..1;
f,v : byte;

procedure read_inp;
var g : text;
i,j : byte;
begin

assign(g,fi);
reset(g);
readln(g,f,v);
for i:=1 to f do
begin

for j:=1 to v do read(g,a[i,j]);
readln(g);

end;
close(g);
end;

procedure solution;

var i,j : byte;
begin

fillchar(c,sizeof(c),0);

t[0] := 0; {cot 0 khoi tri bang 0}
for j:=1 to V do

begin

c[j] := c[j-1];
c[j,j] := 1;

t[j] := t[j-1] + a[j,j];
for i:=j-1 downto 1 do

if t[i] < t[i-1] + a[i,j] then
begin

c[i] := c[i-1];
c[i,j] := 1;

t[i] := t[i-1] + a[i,j];
end;

end;
end;

procedure write_out;
var g : text;

j : byte;
begin

</div>
(84)<div class='page_container' data-page=84>

if c[f,j]=1 then write(g,j,' ');
close(g);

end;
BEGIN

read_inp;
solution;
write_out;
END.

Cách 2b: Cải tiến thêm chút nữa bằng cách thay mảng C[0..mn,0..mn] mỗi phần tử
nhận giá trị 0, 1 bằng mảng C[0..mn, 0..15] mỗi phần tử kiểu byte, viết thêm hàm và thủ
tục quản lý bít.

uses crt;

const fi = 'camhoa.inp';
fo = 'camhoa.out';
mn = 100;

type m1 = array[0..mn,0..mn] of -50..50;
m2 = array[0..mn] of integer;

cachcam = array[0..15] of byte;
m3 = array[0..mn] of cachcam;
var a : m1;

t : m2;
l : m3;
f,v : byte;
procedure read_inp;
var g : text;
i,j : byte;
begin

assign(g,fi);
reset(g);
readln(g,f,v);
for i:=1 to f do
begin

for j:=1 to v do read(g,a[i,j]);
readln(g);

end;
close(g);
end;

function get_bit(i,j : byte): byte;
var nhom, binh : byte;

begin

nhom := j shr 3;
binh := j and 7;

get_bit := (l[i][nhom] shr binh) and 1;
end;

procedure bat_bit(i,j : byte);
var nhom,binh : byte;
begin

</div>
(85)<div class='page_container' data-page=85>

binh := j and 7;

l[i][nhom] := l[i][nhom] or (1 shl binh);
end;

procedure solution;
var i,j : byte;
begin

fillchar(l[0],sizeof(l[0]),0);
t[0] := 0;

for j:=1 to V do
begin

l[j] := l[j-1];
bat_bit(j,j);

t[j] := t[j-1] + a[j,j];
for i:=j-1 downto 1 do

if t[i] < t[i-1] + a[i,j] then
begin

l[i] := l[i-1];
bat_bit(i,j);

t[i] := t[i-1] + a[i,j];
end;

end;
end;

procedure write_out;
var g : text;
j : byte;
begin

assign(g,fo);
rewrite(g);
writeln(t[F]);
for j:=1 to V do

if get_bit(F,j)=1 then write(g,j,' ');
close(g);

end;
BEGIN

read_inp;
solution;
write_out;
END.

IV- các Đề tù gi¶i

1- D·y con

Cho d·y A gåm N sè nguyên dơng và số nguyên dơng K ( N 1000, K50). Tìm dÃy
con nhiều phần tử nhất của dÃy A có tổng các phần tử chia hết cho K

Dữ liệu vào từ file DAYCON.INP:

Dòng đầu là 2 số N và K

Các dòng tiếp theo chứa N số nguyên dơng của dÃy A

Kết quả ghi ra file DAYCON.OUT theo quy cách sau:

</div>
(86)<div class='page_container' data-page=86>

Các dòng tiếp theo ghi L chỉ số của các phần tử của A có mặt trong dÃy con.

2- Trả tiền với số lợng tê Ýt nhÊt

Một Ngân hàng có N loại tiền mệnh giá A[1], A[2], .. ,A[N] với số l ợng tiền mỗi loại
không hạn chế. Cần chi trả cho khách hàng một số tiền là M đồng. Hãy cho biết cần bao
nhiêu tiền mỗi loại để chi trả sao cho số lợng tờ là ít nhất. Hạn chế: N100, A[i] 255,
M10000

D÷ liệu vào từ file văn bản BAI2.INP gồm hai dòng:

Dòng thứ nhất ghi 2 số N và M

Dòng thứ hai ghi N số nguyên dơng A[1], A[2], .. , A[N]

Kết quả ghi ra file văn bản BAI2.OUT theo quy cách sau:

Dòng thứ nhất ghi số k là số lợng tờ phải trả

Các dòng tiếp theo, mỗi dòng ghi 2 số i và SL[i] ( i lµ sè hiƯu vµ SL[i] lµ sè l ợng tờ
loại tiền phải trả)

3- Khoảng cách hai xâu

Cho hai xâu ký tự S1 và S2 mỗi xâu có độ dài không quá 255 ký tự. Cho phép thực hiện
các phép biến đổi sau đây đối với xâu ký tự:

1- Thay thế một ký tự nào đó bởi một ký tự khác.
2- Đổi chỗ hai ký tự liền nhau

3- Chèn vào một ký tự
4- Xoá bớt một ký tự

Ta gọi khoảng cách giữa hai xâu S1 và S2 là số nhỏ nhất các phép biến đổi nêu trên cần
áp dụng đối với xâu S1 để biến nó thành xõu S2.

Yêu cầu: Tính khoảng cách giữa hai xâu S1 và S2 cho trớc.

Ví dụ: S1=Barney, S2 = brawny. Khoảng cách giữa hai xâu S1 và S2 là 4. DÃy c¸c phÐp

biến đổi cần thực hiện là:

Thay ký tù 1 của S1 là B thành b

Đổi chỗ hai ký tự thø hai lµ ‘a’ vµ thø ba lµ ‘r’
ChÌn ký tù ‘w’ vµo sau ký tù thø ba

Xố ký tự thứ sáu trong S1 đang biến đổi là ‘e’
Dãy phép biến đổi có thể mơ tả nh sau:

‘Barney’ ‘barney’ ‘braney’ brawney brawny

Dữ liệu vào từ file văn bản STREDIT.INP có cấu trúc nh sau:

Dòng đầu tiên chứa xâu S1
Dòng thứ hai chứa xâu S2

</div>
(87)<div class='page_container' data-page=87>

Dũng đầu tiên ghi số lợng phép biến đổi cần sử dụng là số k

 Mỗi dòng thứ i trong k dịng tiếp theo mơ tả phép biến đổi đợc sử dụng ở lần thứ i
(i=1,2,..,k): đầu tiên ghi chỉ số của phép biến đổi đợc sử dụng, tiếp đến :

+ Nếu là phép biến đổi 1 cần chỉ ra vị trí của ký tự cần thay thế trong xâu đang biến
đổi và ký tự thay thế

+ Nếu là phép biến đổi 2 cần chỉ ra vị trí (xếp theo thứ tự tăng) của hai ký tự cần đổi
chỗ

+ Nếu là phép biến đổi 3 cần chỉ ra vị trí ký tự trong xâu đang xét mà sau nó cần
chèn một ký tự và ký tự cần chèn

+ Nếu là phép biến đổi 4 cần chỉ ra vị trí của ký tự cần xố trong xâu đang xét.

VÝ dơ:

STREDIT.INP STREDIT.OUT

Barney

Brawny 41 1 b

2 2 3
3 3 w
4 6

4- Bµi thi häc sinh giái 1995-1996 - Bµi 4

Víi N nguyên dơng, xét TN là tập tất cả các dÃy số nguyên không âm A=(a0, a1, ..,a2k)
thoả mÃn các ®iỊu kiƯn:

1 k N (1)

a0 = a2k = 0 (2)

| ai - ai+1 | = 1 víi i=0, 1, 2, .. , 2k-1 (3)

ta định nghĩa quan hệ thứ tự từ điển “<” trên tập TN nh sau: Hai dãy số X=(x0,
x1, .. , xp) và Y=(y0, y1,, .., yp) thuộc tập TN có quan hệ X<Y nếu tồn tại 0  r  min(p,q)
sao cho xi = yi , i  r đồng thời r=p hoặc xr+1 < yr+1.

Các dãy số trong tập TN đợc sắp xếp theo thứ tự từ điển và đợc đánh số từ 1 trở đi.
Ví dụ: với N=3 tập TN gồm 8 phần tử và thứ tự của chúng nh sau

</div>
(88)<div class='page_container' data-page=88>

7 (0 1 2 1 2 1 0)

8 (0 1 2 3 2 1 0)

Yêu cầu:

a) Với N cho trớc, tính tỉng sè c¸c d·y thc TN

b) Với M ngun cho trớc tìm dãy có thứ tự từ điển là M trong tập TN
c) Với một dãy cho trớc thuộc tập TN xác định thứ tự từ điển của nó.

D÷ liƯu vào file văn bản BL4.INP:

Dòng thứ nhất: N (N nguyên dơng, N 46)

Các dòng tiếp theo: mỗi dòng có thể có một trong hai dạng:
1 M

hoặc 2 k a0 a1 . . . a2k

các số trên một dòng cách nhau ít nhất một dấu cách.

Dạng đầu là dữ liệu cho câu hỏi b), dạng sau là dữ liệu cho câu hỏi c). Tổng số các dòng
cho các câu hỏi loại b), c) là không quá 50.

Kết quả đa ra file văn bản BL4.OUT

Dòng đầu: số nguyên cho biết tổng số các dÃy trong tËp TN

Các dòng sau: mỗi dòng tơng ứng với một dòng yêu cầu trong dữ liệu vào. Với câu hỏi
b) kết quả là dãy a0, a1, . . . ,a2k các số đa ra trên một dòng, cách nhau ít nhất một dấu
cách, quy ớc ghi số 0 nếu khơng có dãy thoả mãn điều kiện đặt. Với câu hỏi c) kết quả

là số nguyên M, đa ra trên một dịng.

5- Xố đơn điệu k-gián đoạn

Cho một dãy số nguyên gồm N số hạng A[1], A[2], . . , A[N], N1000 các số hạng
có trị tuyệt đối khơng q 30000 và một số nguyên dơng K. Hãy tìm cách xố đi một số
ít nhất số hạng sao cho dãy còn lại là một dãy đơn điệu tăng ngoại trừ không quá K cặp
số liền nhau vi phạm điều kiện này.

Dữ liệu vào đợc cho từ file DAYK.INP trong đó dịng thứ nhất ghi hai số N và K,

K10. Trong N dòng tiếp theo, mỗi dòng ghi một số hạng của dÃy bắt đầu từ A[1] và
cuối cùng là A[N].

Kết quả ghi ra file DAYK.OUT nh sau: Dòng thứ nhất ghi số B là số số hạng xoá ®i.

Nếu B >0, trong B dòng tiếp theo, mỗi dòng ghi chỉ số của một số hạng bị xoá đi theo
thứ tự tăng dần. Tiếp theo là một dòng ghi số M là số vi phạm tính đơn điệu, nếu M>0,
trong M dòng tiếp theo, mỗi dòng ghi một chỉ số U với ý nghĩa tại đó điều kiện đơn điệu
bị vi phạm tức là A[U] là số hạng còn lại nhng số hạng cịn lại tiếp theo khơng lớn hơn
A[U], các chỉ số U cũng ghi theo thứ tự tăng dần.

VÝ dơ:

DAYK.INP DAYK.OUT

</div>
(89)<div class='page_container' data-page=89>

1
2
3
2

1
3

6- Th¸p Babylon

Tháp Babylon xây bằng n loại khối đá hình hộp chữ nhật có kích thớc (xi, yi ,zi ) (1
i  n ) theo nguyên tắc một khối đá chỉ có thể đặt trên khối khác khi và chỉ khi cả hai
kích thớc đáy của khối ở trên nhỏ hơn kích thớc tơng ứng của đáy khối dới . Hãy lập
trình xây dựng tháp sao cho tháp cao nhất. Mỗi loại khối đá có thể dùng nhiều lần

Input : cho trong file "BABYLON.INP" : Dòng đầu là số n. N dòng sau , mỗi dòng ghi
3 số xi yi zi lµ kÝch thíc khèi cã sè hiƯu i

Output : ghi ra file "BABYLON.OUT" theo quy cách :
+ Dòng đầu ghi độ cao của tháp .

+ Dòng thứ hai ghi số m là số lợng khối đá có thể dùng xây tháp

+ m dòng tiếp theo lần lợt ghi các khối xếp từ đáy tháp lên đỉnh , mỗi dòng gồm 4 số k,
a, b, c , trong đó k là số hiệu khối đá, a và b là 2 kích thớc chọn làm đáy, c là kích thớc
chọn làm chiều cao.

BABYLON.INP

2 6 8 10

5 5 5

BABYLON.OUT

21

3 1 8 10 6

1 6 8 10

2 5 5 5

7- Khăn trải bàn

Quy n của một khách sạn cần
sử dụng K[1], K[2], . ., K[N] khăn
trải bàn cho N ngày liên tiếp đánh số
từ 1 đến N. Khách sạn có thể mua
khăn trải bàn mới với giá A đồng
một khăn, hoặc thuê hiệu giặt trả

nhanh (nhận lại khăn giặt sạch vào
ngày hôm sau) với giá B đồng một
khăn, hoặc thuê hiệu giặt thờng trả
lại khăn sau 2 ngày (nhận vào ngày i,
trả vào ngày i+2) với giá C đồng một
khăn. Giả sử trong ngày đầu tiên
khách sạn cha có khăn. Hãy lập kế
hoạch mua và giặt khăn bảo đảm yêu
cầu về khăn cho N ngày với chi phớ
nh nht.

Dữ liệu vào từ file BAI7.INP

gồm 2 dòng

Dòng thứ nhất là 4 số nguyên
d-ơng N, A, B, C (N<100, C<B<A)
 Dßng thø hai gåm N sè nguyên

dơng K[1], K[2], . ., K[N]

</div>
(90)<div class='page_container' data-page=90>

Kết qu¶ ghi ra file văn bản

BAI7.OUT gồm N+1 dòng:

Dßng thø nhÊt ghi tæng chi phÝ
nhá nhÊt

 Dßng i+1 (1iN) ghi 3 số
nguyên không âm M[i], F[i], S[i]
theo thứ tự là số khăn cần mua,
giặt trả nhanh, giặt trả bình thờng
trong ngày i.

8- Xây dựng cây nhị phân t×m
kiÕm tèi u:

Mỗi nút i của cây nhị phân có
một khố là f[i]. Mỗi lần truy xuất
tới nút i, phải đi qua d[i] nút khác
(gọi d[i] là khoảng cách từ gốc đến
nút i). Ta gọi giá thành truy xuất tới
nút i là C[i]=f[i]*d[i] và gọi cost là

độ dài đờng đi trong có trọng số của
cây, đó là tổng các giá thành truy
xuất tới các nút của cây nhị phân.

Cost =



C[i]
1iN

Bài toán đặt ra là cho N nút với
khoá của từng nút, xây dựng cây nhị
phân mà độ dài đờng đi trong có
trọng số của cây có giá trị nhỏ nhất
trong tập tất cả các cây có cùng tập
nút (khố cho trớc).

9- XÕp lÞch häc tËp

Mét anh sinh viên khoa công
nghệ thông tin (do mải chơi nªn lËp

trình cha khá !) đang băn khoăn
không biết phải phân phối thời gian
học N môn nh thế nào trong một
khoảng thời gian còn lại là T. Mỗi
mơn học i có số học trình là Si (Khi
tính điểm tổng kết, điểm thi một
mơn đợc nhân với số học trình Si của
mơn đó vì số học trình càng cao thì
lợng kiến thức đào tạo của mơn đó
càng nhiều).

Kết quả của môn học tuỳ
thuộc lợng thời gian anh ta dành cho
môn đó. Anh ta khơng muốn thi lại
bất cứ môn nào và muốn có điểm
tổng kết cao nhất.

Em hãy lập trình giúp anh
sinh viên đó phân phi thi gian hc
cỏc mụn?

File Input

+ Dòng đầu là hai số N và T

+ Dòng thứ hai là n sè Si (1  i 
N)

+ N dòng tiếp theo: dòng thứ i trong
N dòng này chứa 6 số thể hiện số giờ
tối thiểu để anh ta đạt đợc điểm lần
lợt là 5 đến 10.

File Output

+ Dòng đầu là tổng điểm của N môn

(ó tớnh h số học trình)

+ N dßng tiÕp theo, dßng thø i là thời

gian mà anh ta đầu t cho môn thứ i.

VÝ dô:
HOCTRINH.IN

3 12
1 2 2

</div>
(91)<div class='page_container' data-page=91>

HOCTRINH.OUT
43

1
5
6

10 - M· ho¸:

Cho một nguyên bản S là xâu ký tự
chỉ gồm các chữ cái có độ dài khơng
q 250. Bản đã mã hoá của S đợc
ký hiệu là C(S) gồm các cặp (Pi, Ri)
thoả mãn:

 NÕu Pi = 0 thì Ri là ký tự chữ cái
Nếu Pi > 0 th× Ri lµ mét số

nguyên mà Pi Ri >0

Vic gii bn mó C(S) c tin hnh
nh sau:

Trớc hết tạo xâu S0 rỗng

Giả sử đã giải mã đến bớc thứ i
đợc xâu Si, giải mã ở bớc tiếp
theo i+1 nh sau:

+ Nếu Pi+1 = 0 thì Si+1 = Si + Ri+1
+ Nếu Pi+1 >0 thì Si+1 = Si + W trong
đó W là xâu gồm Ri+1 ký tự liên tiếp
của Si bắt đầu từ ký tự thứ Pi+1 tính từ
cuối xâu Si

VÝ dơ:

C(S)=(0,a), (1,1), (0,b), (3,3), (3,3),
(3,2), (0,c) thì nguyên b¶n
S=aabaabaabaac

Bài tốn đặt ra là:

1- Cho bản mã C mã hoá theo đúng
quy cách trên, hãy khôi phục
nguyên bản S

2- Với nguyên bản S nhận đợc, hãy
tìm cách mã hoá theo quy định
trên sao cho có bản mã C' với số
cặp ít nhất có thể đợc

Dữ liệu vào cho bởi file văn bản
MAHOA.INP trong đó dịng thứ
nhất ghi số k là số cặp mã của bản
mã C(S). Trong k dòng tiếp theo:
dòng thứ i ghi 2 giá trị Pi và Ri (chú
ý Ri là chữ số khi Pi=0 và là ký tự khi
Pi>0).

</div>

QhdongDOC

<b>I.</b>

<b>Quy hoạch động</b>

1. Phơng pháp quy hoạch động

2. Các bớc thực hiện

3. Hạn chế của quy hoch ng

4. Mt vi vớ d

<b>II.</b>

<b>Một số bài toán tiêu biểu</b>

(Phát biểu, phân tích thuật toán và tổ chức dữ liệu, chơng trình)

<b>III.</b>

<b>Các bài tập luyện tập</b>

1. Đề bµi

2. Híng dÉn

<b>IV.</b>

<b>Các đề tự giải</b>

∑

∑

L[i,j,u,h,r]=

<b>Min</b>

{L[i,j,u,h,r],L[d[m,1],d[m,2],d[m,3],d[m,4],d[m,5]]+

L[i-d[m,1],j-d[m,2],u-d[m,3],h-d[m,4],r-d[m,5]])}

Sl1=

Sl2=



BABYLON.INP

2

6 8 10

5 5 5

BABYLON.OUT

21

3

1 8 10 6

1

6 8 10

2

5 5 5



Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về