1

Lời nói đầu

Lập trình động (còn gọi là phương pháp quy hoạch động) là một kĩ thuật rất

hiệu quả giải quyết nhiều bài toán tin học, đặc biệt là những bài toán tối ưu. Số

lượng bài toán được giải bằng lập trình động cũng rất lớn, ví dụ riêng kì thi

Olympic quốc tế về Tin học IOI 2004 có tới 3 bài trong 6 bài thi có thể giải bằng

lập trình động. Nhiều năm gần đây, trong hầu hết các đề thi chọn HSG QG đều

có ít nhất 1 trong 3 bài có thể giải bằng phương pháp quy hoạch động.

Nhóm tác giả chúng tôi biên tập tài liệu “Bài tập quy hoạch động” này

mong muốn giới thiệu lí thuyết và các bài tập từ đơn giản đến phức tạp của lập

trình động. Cuốn sách sẽ là tài liệu quí báu đối với học sinh năng khiếu Tin học,

sinh viên các ngành công nghệ thông tin và giáo viên môn Tin học của các

trường THPT.

Tài liệu gồm 4 chương:

Chương I: Cơ sở lý thuyết

Chương II: Một số bài tập cơ bản

Chương III: Bài tập chọn lọc

Chương IV: Một số đề tự giải

Chương I nêu rõ tư tưởng, vị trí, ứng dụng của lập trình động và cách nhận

diện các bài tập có thể giải bằng phương pháp quy hoạch động. Chương II phân

tích và dẫn ra chương trình giải các bài toán kinh điển như: Tìm dãy con không

giảm dài nhất, Dãy con chung dài nhất, Tìm dãy con có tổng bằng S, ….Chương

III, chương IV giới thiệu đề bài, cách giải, chương trình của rất nhiều bài tập

chọn lọc.

Chúng tôi chân thành cảm ơn các bạn đồng nghiệp đã nhận xét và góp ý

cho bản thảo, trân trọng cảm ơn BGH trường THPT Chuyên Bắc Giang đã khích

lệ, tạo điều kiện cho nhóm tác giả được nghiên cứu để tài liệu sớm được ra mắt

bạn đọc.

2

Trong quá trình biên soạn, mặc dù chúng tôi đã cố gắng, song nội dung

chuyên đề ngày càng có nhiều khía cạnh mới và sâu sắc nên chắc chắn tài liệu

còn nhiều hạn chế. Chúng tôi rất mong được bạn đọc xa gần góp ý, để lần tái bản

sau tài liệu sẽ hoàn thiện hơn.

Mọi góp ý, xin gửi đến địa chỉ:

Nhóm Tin học Trường THPT Chuyên Bắc Giang

3

Chương I:

Cơ sở lý thuyết

I.1. Tư tưởng của phương pháp quy ho ạch động

I.1.1. Thuật toán chia để trị

Lập trình động cũng như chia để trị là các phương pháp giải một bài toán

bằng cách tổ hợp lời giải các bài toán con của nó.

Thuật toán chia để trị được coi là thuật toán thông dụng nhất trong Tin

học. Khi giải một bài toán P với kích thước ban đầu nào đó nếu gặp trở ngại vì

kích thước quá lớn, người ta thường nghĩ đến việc giải các bài toán tương tự

nhưng với kích thước nhỏ hơn (gọi là các bài toán con của P). Tư tưởng “chia để

trị” thường được nhắc tới như hình ảnh “bẻ dần từng chiếc đũa để bẻ gãy cả

bó đũa”.

Chia để trị thực hiện “tách” một bài toán ban đầu thành các bài toán con

độc lập, sau đó giải các các bài toán con này và tổ hợp dần lời giải từ bài toán

con nhỏ nhất đến bài toán ban đầu.

Nhưng giải từng bài toán con như thế nào? Chúng ta có thể thực hiện một

cách đơn giản lại “tách” bài toán con thành các bài toán con nhỏ hơn nữa, và

cứ tiến hành như vậy cho đến khi gặp các bài toán con nhỏ đến mức dễ dàng

giải được. Các bài toán con cùng được sinh ra sau mỗi lần “tách” được gọi là

cùng mức. Những bài toán con sinh ra sau hơn thì ở mức dưới (thấp hơn).

Thủ tục đệ quy luôn là cách thường dùng và hiệu quả để thực hiện thuật

toán chia để trị. Quá trình đệ quy lần lượt xếp dần các bài toán con vào ngăn

xếp bộ nhớ và sẽ thực hiện giải các bài toán con theo thứ tự ngược lại từ bài

toán đơn giản nhất trên đỉnh ngăn xếp cho đến khi giải được bài toán ban đầu

ở đáy ngăn xếp.

Ví dụ: Cho mảng a[1..n] gồm các số đã sắp tăng. Tìm phần tử của mảng có

giá trị bằng số x cho trước.

4

Xét chương trình thực hiện thuật toán tìm kiếm nhị phân (một kiểu chia

để trị rất phổ biến) để giải bài toán trên. Trong chương trình chính có lời gọi

thủ tục tim(1,n). Sau đây là thủ tục tim(i,j):

Procedure tim(i,j : integer); {Tim x c ó trong mảng a[i .. j] hay không}

Var k : integer;

Begin

K := (i+j) div 2;

If a[k] = x then

Begin

Write(‘Co phan tu bang ‘,x);

Halt;

End

Else

If (a[k] < x) and (k<j) then tim(k+1,j)

Else

If (a[k] > x) and (k>i) then tim(i,k-1)

End;

Do chỉ tìm kiếm trên một trong hai phần được “tách” ra, nên độ phức tạp

thuật toán là O(log

2

n), tốt hơn là tìm kiếm tuần tự.

I.1.2. Hệ thức truy hồi

Giải bài toán thường tiến hành theo nhiều bước. Kết quả của một bước

thường dựa vào kết quả của các bước thực hiện trước đó. Do vậy, cần xây

dựng hệ thức thể hiện quan hệ về kết quả giữa các bước gọi là hệ thức truy

hồi.

Ví dụ 1: Cho dãy số Fibonaci {F

1

, F

2

, …, F

n

}, trong đó:

F

1

= F

2

= 1 và F

n

= F

n-1

+ F

n-2

với n > 2 (1). Tìm số hạng thứ n.

5

Hệ thức tính số hạng thứ n của dãy Fibonaci là hệ thức (1) đã cho sẵn

trong đề bài.

Ví dụ 2: Cho một dãy N số nguyên A

1

, A

2

, …, A

n

. Hãy tìm cách xoá đi một số

ít nhất số hạng để dãy còn lại là đơn điệu hay nói cách khác 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.

Minh hoạ cho ví dụ 2:

Dãy A: 1, 4, 10, 9, 8, 17, 11, 7, 12, 6

Dãy B: 1,4,10,11,12

Phân tích để giải bài toán ta thấy:

Khi dãy A có một phần tử a1thì dãy B có 1 phần tử.

Mở rộng bài toán với dãy A có 2 phần tử, có 3 phần tử, … để tìm độ dài

dãy B. Ta có bài toán tổng quát: Gọi F[i] là số phần tử của dãy con B khi dãy A

có các phần tử từ 1 đến i

Dễ dàng tính được:

F[i] := 1 nếu không tồn tại j:= 1..i-1 để A[j] < A[i]

F[i] := max{F[j], j=1..i-1 thoả mãn a[j] < a[i]} + 1; (2)

Như vậy, để giải bài toán ở ví dụ 2 ta phải tiến hành qua n bước. lời giải ở

bước i (i=1,2,…,n) phụ thuộc vào lời giải của i-1 bước trước đó. Hệ thức (2)

chính là hệ thức truy hồi của bài toán.

I.1.3. Lập trình động là gì?

Lập trình động giống phương pháp chia để trị ở chỗ: lời giải của bài toán

được tổ hợp từ lời giải các bài toán con.

“Chia để trị” sẽ phân chia bài toán ban đầu thành các bài toán con độc lập

(sự phân chia có cấu trúc dạng cây), giải các bài toán con này thường bằng đệ

quy, sau đó tổ hợp lời giải của chúng để được lời giải của bài toán ban đầu.

6

Lập trình động (dynamic programming) cũng phân chia bài toán thành các

bài toán con, nhưng các bài toán con phụ thuộc nhau (hay dùng từ gối nhau

cũng được), mỗi bài toán con có thể tham chiếu tới cùng một số bài toán con

mức dưới (sự phân chia không có cấu trúc dạng cây xem hình 1).

Hình 1: Đồ thị bài toán con cho dãy Fibonacci. Đây không phải là một

cấu

trúc cây

mà là một

đồ thị có hướng phi chu trình

mô tả quan hệ giữa các bài

toán con gối nhau.

Nói rằng một bài toán có các bài toán con trùng nhau có nghĩa là mỗi bài

toán con đó được sử dụng để giải nhiều bài toán lớn hơn khác nhau. Ví dụ,

trong

dãy Fibonacci

, F

3

= F

1

+ F

2

and F

4

= F

2

+ F

3

— khi tính mỗi số đều phải tính

F

2

. Vì tính F

5

cần đến cả F

3

và F

4

, một cách tính F

5

một cách ngây thơ có thể sẽ

phải tính F

2

hai lần hoặc nhiều hơn. Điều này áp dụng mỗi khi có mặt các bài

toán con gối nhau: một cách tiếp cận ngây thơ có thể tốn thời gian tính toán lại

lời giải tối ưu cho các bài toán con mà nó đ ã giải.

Để tránh việc đó, ta lưu trữ lời giải của các bài toán con đã giải. Do vậy,

nếu sau này ta cần giải lại chính bài toán đó, ta có thể lấy và sử dụng kết quả

đã được tính toán. Hướng tiếp cận này được gọi là lưu trữ (trong

tiếng Anh

được gọi là

memoization

, không phải memorization, dù từ này cũng hợp nghĩa).

Nếu ta chắc chắn rằng một lời giải nào đó không còn cần thiết nữa, ta có thể

xóa nó đi để tiết kiệm không gian bộ nhớ. Trong một số trường hợp, ta còn có

thể tính lời giải cho các bài toán con mà ta biết trước rằng sẽ cần đến.

7

Khi giải bài toán Fibonaci cỡ i (với i tăng từ 2 đến n), ta đều sử dụng kết

quả của 2 bài toán con cỡ i-1 và i-2;

Lập trình động do nhà toán học người Mỹ là Richard Bellman (1920-1984)

phát minh vào năm 1953.

Lập trình động thường dùng để giải các bài toán tối ưu – bài toán yêu cầu

tìm một giải pháp tốt nhất trong các giải pháp có thể tìm được.

Cơ sở của lập trình động trong bài toán tối ưu là nguyên lí tối ưu Bellman:

“Dãy tối ưu các quyết định trong một quá trình quyết định nhiều giai đoạn có

thuộc tính là dù trạng thái và các quyết định ban đầu bất kể thế nào, những

quyết định còn lại phải tạo thành một cách giải quyết tối ưu không phụ thuộc

vào trạng thái được sinh ra từ những quyết định ban đầu”

I.1.4. Phương pháp quy hoạch động

Trong ngành khoa học máy tính, phương pháp quy hoạch động là một

phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của

các bài toán con gối nhau và cấu trúc con tối ưu.

Tư tưởng chủ đạo của phương pháp quy hoạch động có thể tóm lược như

sau:

Chia 1 bài toán lớn thành các bài toán con tương tự có kích thước nhỏ hơn

cho đến khi nhận được các bài toán con mà lời giải có thể xây dựng dễ dàng.

Ta phải tìm ra mối quan hệ giữa nghiệm của bài toán với nghiệm của các

bài toán con, mối quan hệ thể hiện 1 công thức truy hồi hay một hàm gọi là

công thức quy hoạch động (hay hàm quy hoạch động).

Khi tính toán chúng ta xuất phát tính từ nghiệm các bài toán con ban đầu,

sau đó kết hợp nghiệm của các bài toán con theo công th ức quy hoạch động ta

được nghiệm bài toán con có cỡ lớn hơn. Quá trình cứ tiếp tục như vậy cho

đến khi ta được nghiệm của bài toán đã cho.

8

Vậy: Ý tưởng cơ bản của quy hoạch động thật đơn giản: tránh tính toán

lại mọi thứ hai lần, mà lưu giữ kết quả đã tìm kiếm được vào một bảng làm giả

thiết cho việc tìm kiếm những kết quả của trường hợp sau. Chúng ta sẽ làm

đầy dần giá trị của bảng này bởi các kết quả của những trường hợp trước đã

được giải. Kết quả cuối cùng chính là kết quả của bài toán cần giải

Ví dụ: Tính số hạng thứ n của dãy Fibonaci bằng phương pháp quy hoạch

động như sau:

Nghiệm của mỗi bài toán con chỉ cần tính 1 lần và được lưu trong mảng 1

chiều F. Khi tìm kết quả của các bài toán cỡ lớn hơn, kết quả của các bài toán

con chỉ việc lấy ra để sử dụng.

F1 := 1; F2 := 1;

For i := 3 to n do F[i] := F[i-2] + F[i-1];

I.2. Các bước thực hiện giải bài toán bằng phương pháp quy

hoạch động

I.2.1. Các bước cơ bản:

Bước 1: Phân tích tìm công thức quy hoạch động

- Tìm ra công thức nghiệm của bài toán lớn thông qua việc giải các bài

toán con.

- Xác định nghiệm của bài toán con đơn giản (trong trường hợp cơ sở)

Bước 2: Thực hiện tính toán và tổ chức dữ liệu

- Đầu tiên tính nghiệm của bài toán con đơn giản (cơ sở)

(Khởi tạo giá trị ban đầu cho hàm QHĐ)

- Dựa vào hàm QHĐ đã xây dựng ta tính nghiệm của bài toán theo kích

thước lớn dần cho đến khi nhận được nghiệm của bài toán đã cho.

Bước 3: Tổ chức dữ liệu và cài đặt

9

- Thường dùng mảng một chiều hoặc hai chiều để lưu trữ lại các giá trị

của các bài toán con (giá trị của hàm QHĐ)

- Ngoài ra, chúng ta phải dùng một số biến, thông thường cũng là mảng để

lưu trữ lại trạng thái của bài toán để sau này chúng ta có thể truy xuất lời giải

của bài toán.

I.2.2. Tổ chức cài đặt:

- Có thể dùng vòng lặp

- Hoặc dùng đệ quy

- Nghiệm của các bài toán con được tính toán 1 lần và lưu trữ trong mảng

khi cần lấy ở mảng đó ra và sử dụng

I.2.3 Khi nào dùng phương pháp quy hoạch động?

- Khi gặp bài toán có tính chất truy hồi

- Khi lời giải bài toán ở bước sau được xây dựng thông qua lời giải bài

toán ở bước trước.

- Kích thước bài toán không quá lớn

*Ưu điểm:

- Lời giải ngắn gọn, sang sủa, có tính logic cao, chương trình chạy nhanh.

*Nhược điểm:

- Không phải bài nào cũng giải bằng QHĐ

- Việc tìm ra công thức QHĐ của nhiều bài toán là khó khăn

- Không có công thức chung

- Bị hạn chế về bộ nhớ vì chúng ta phải lưu trữ nghiệm của các bài toán

con.

10

Chương II:

Một số bài tập cơ bản

Bài 1: Tìm dãy con không gi ảm nhiều phần tử nhất;

Cho dãy số nguyên có n phần tử a

1

, a

2

, …, a

n

. Một dãy con không giảm của

dãy đã cho là dãy các phần tử còn lại của dãy đó sau khi ta xóa bỏ một hoặc

một số phần tử bất kì của nó, các phần tử của dãy con tạo thành dãy không

giảm. Ví dụ: dãy 1,4,10,11,12 là một dãy con không giảm của dãy 1, 4, 10, 9, 8,

17, 11, 7, 12, 6.

Yêu cầu: Tìm dãy con không giảm của dãy a gồm nhiều phần tử nhất.

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

Dòng đầu tiên ghi số N (0 < N < 10

5

).

Các dòng tiếp theo, mỗi dòng ghi 10 số nguyên của dãy N số nguyên a

1

, a

2

,

.., a

n

. Dòng cuối cùng có thể ít hơn 10 số. Các số trên một dòng cách nhau một

dấu cách.

Kết quả: Ghi ra file văn bản DAYCON.OUT gồm:

Số max là độ dài dãy con không giảm dài nhất tìm được.

Chỉ số xuất hiện của các số hạng của dãy con trong dãy đã cho.

Ví dụ:

DAYCON.INP

DAYCON.OUT

10

6 5 8 12 6 9 7 13 2 13

5

2 5 7 8 10

Hướng dẫn:

Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a

1

đến a

i

và phần tử cuối cùng là a

i

.

Ta có công thức QHĐ để tính L(i) như sau:

L(1) = 1

L(i) = max(1, L(j)+1 với mọi phần tử j: 0 < j < i và a

j

≤ a

i

).

11

Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm

QHĐ L(i). Đoạn chương trình tính các giá trị của mảng L như sau:

for i := 1 to n do

begin

L[i] := 1;

for j:=1 to i - 1 do

if (a[j]<=a[i]) and (L[i]<L[j]) then L[i]:=L[j]+1;

end;

Như vậy chi phí không gian của bài toán là O(n), chi phí th ời gian là O(n

2

).

* Chương trình cài đặt:

program day_con_khong_giam_dai_nhat;

uses crt;

const fi='DAYCON.inp';

fo='DAYCON.out';

max=100000;

type arrA=array[0..max]of longint;

arrB=array[1..max,1..max]of longint;

var f:text;

a:arrA;

n,kq,luu,dem:longint;

d,truoc,k:arrA;

procedure init;

var i:longint;

begin

assign(f,fi);

reset(f);

12

readln(f,n);

for i:=1 to n do

read(f,a[i]);

close(f);

end;

procedure process;

var i,j:longint;

begin

for i:=1 to n do

truoc[i]:=i;

d[1]:=1;

for i:=1 to n do

begin

d[i]:=1;

for j:=1 to i-1 do

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

if d[j]+1>d[i] then

begin

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

truoc[i]:=j;

end;

end;

kq:=0;

for i:=1 to n do

if d[i]>kq then begin kq:=d[i];luu:=i;end;

dem:=0;

13

while truoc[luu]<>luu do

begin

inc(dem);

k[dem]:=luu;

luu:=truoc[luu];

end;

inc(dem);

k[dem]:=luu;

end;

procedure inkq;

var i:longint;

begin

assign(f,fo);

rewrite(f);

writeln(f,kq);

for i:=dem downto 1 do

write(f,k[i],' ');

close(f);

end;

BEGIN

init;

process;

inkq;

END.

Bài 2: Dãy con chung dài nhất;

Cho hai dãy số nguyên a = (a

1

, a

2

, …, a

M

), b = (b

1

, b

2

, …, b

N

), với M,N < 200.

14

Hãy tìm một dãy con chung c=(c

1

, c

2

, …, c

K

) của a và b gồm nhiều số hạng

nhất. Dãy con chung c nhận được bằng cách xóa đi một số số hạng của dãy a, c

cũng nhận được bằng cách xóa đi một số số hạng của dãy b, sau khi xóa ở hai

dãy giữ nguyên thứ tự các phần tử còn lại.

Dữ liệu: Vào từ file văn bản DAYCC.INP có cấu trúc như sau:

Dòng đầu tiên ghi 2 số nguyên dương M, N.

Dòng thứ 2 ghi các số a

1

, a

2

, …, a

M

;

Dòng thứ 3 ghi các số b

1

, b

2

, …, b

N

;

Kết quả: Ghi ra file văn bản DAYCC.OUT có cấu trúc:

Dòng đầu ghi số K là số lượng các số hạng của dãy con chung c (nếu không

có dãy con chung thì ghi số 0);

Trong k dòng tiếp theo, dòng thứ i (I = 1, 2, .., k) ghi 2 số x, y với ý nghĩa là:

số hạng thứ i của dãy c là số hạng thứ x của dãy a và là số hạng thứ y của dãy

b;

Ví dụ:

DAYCC.INP

DAYCC.OUT

7 6

3 5 1 3 5 5 3

1 5 3 5 3 1

4

2 2

4 3

6 4

7 5

*Hướng dẫn:

Gọi L(i,j) là độ dài dãy con chung dài nhất của dãy a(i) gồm i phần tử

phần đầu của dãy a (a(i) = a[1..i]) và dãy b(j) gồm j phần tử phần đầu của dãy b

15

(b(j)

=b [1..j]).

Ta có công thức quy hoạch động như sau:

L(0,j)=L(i,0)=0.

L(i,j) = L(i - 1,j - 1)+1 nếu a[i] = b[j].

L(i,j) = max(L(i - 1,j), L(i,j - 1)) nếu a[i] ≠ b[j].

*Chương trình cài đặt:

Program Dayconchung;

uses crt;

const fi='daycc.inp';

fo='daycc.out';

maxmn=100;

var f:array[0..maxmn,0..maxmn] of integer;

g:text;

m,n:integer;

a,b:array[1..maxmn] of integer;

Procedure init;

var i:integer;

Begin

assign(g,fi); reset(g);

readln(g,m,n);

for i:=1 to m do read(g,a[i]);

for i:=1 to n do read(g,b[i]);

close(g);

End;

Function max(x,y:integer):integer;

Begin

16

if x > y then max:=x else max:=y;

End;

Procedure Build;

var i,j:integer;

Begin

for i:= 0 to m do f[i,0]:=0;

for i:= 0 to n do f[0,i]:=0;

for i:=1 to m do

for j:=1 to n do

if a[i] <> b[j] then f[i,j] := max(f[i-1,j],f[i,j-1])

else f[i,j] := f[i-1,j-1] + 1;

End;

Procedure result;

var i,j:integer;

Begin

assign(g,fo); rewrite(g);

writeln(g,f[m,n]);

i := m; j := n;

while (i<>0) and (j<>0) do
Begin
if a[i] = b[j] then
Begin
writeln(g,i,' ',j);
dec(i);
dec(j);
End
else

17

Begin
if f[i,j] = f[i-1,j] then dec(i)
else if f[i,j] = f[i,j-1] then dec(j);
end;

end;

close(g);

End;

BEGIN

init;

build;

result;

END.

Bài 3: Dãy con có tổng bằng S

Cho dãy a

1

, a

2

,.. a

n

. Tìm một dãy con của dãy đó có tổng bằng S.

Dữ liệu: vào từ file văn bản "tongs.inp" có dạng :

- Dòng đầu tiên là 2 số N, S (N<200);

- Dòng thứ hai là N số A

i

(i=1, 2,.., N; -32000 <= A

i

<=32000).

Kết quả: Ghi ra file văn bản "tongs.out" có dạng:

- Các phần tử thuộc dãy con tìm được

Ví dụ:

tongs.inp

Tongs.out

8 39

19 5 20 13 16 20 18 2

19 20

* Hướng dẫn:

18

Đặt L(i,t)=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các

phần tử a

1

,a

2

,..a

i

. Ngược lại thì L(i,t)=0. Nếu L(n,S)=1 thì đáp án của bài toán

trên

là

'có'.

Ta có thể tính L(i,t) theo công thức: L(i,t) = 1 nếu L(i - 1,t)=1 hoặc L(i-1,t -

a[i])=1.

* Chương trình cài đặt:

Program day_con_tong_s;

uses crt;

const fi='tongs.inp';

fo='tongs.out';

max=6400;

maxn=200;

type arrA=array[1..maxn]of longint;

arrB=array[0..max]of longint;

var f:text;

n:longint;

a,truoc:arrA;

s:longint;

d:arrB;

procedure init;

var i:longint;

begin

assign(f,fi);

reset(f);

readln(f,n,s);

for i:=1 to n do

19

read(f,a[i]);

close(f);

end;

procedure process;

var i,j:longint;

begin

for i:=1 to s do d[i]:=0;

for i:=1 to n do

for j:=s downto a[i] do

begin

if (d[j]=0) and (d[j -a[i]]=1) then

begin

d[j]:=1;

truoc[j]:=i;

end;

if d[s]<>0 then exit;

end;

end;

procedure inkq;

var i:longint ;

begin

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

if d[s]=0 then write(f,'0')

else

begin

i:=truoc[s];

20

while s<>a[i] do

begin

write(f,a[i],' ');

s:=s-a[i];

i:=truoc[s];

end;

write(f,a[i]);

end;

close(f);

end;

BEGIN

init;

process;

inkq;

END.

Bài 4: Xếp đồ vật vào ba lô (mỗi đồ vật chỉ có 1)

Một chiếc ba lô có thể chứa được một khối lượng không quá W. Có N đồ

vật được đánh số từ 1 đến N, đồ vật i có khối lượng A

i

và giá trị sử dụng C

i

(i=1,

2, …,N). Hãy chọn các đồ vật để xếp vào ba lô sao cho tổng giá trị các đồ vật

trong ba lô là lớn nhất (nếu có thể xếp được).

Dữ liệu: vào từ file văn bản BALO.INP có cấu trúc như sau:

Dòng đầu ghi 2 số nguyên dương N, W (0 < N,W < 100).

Dòng thứ i+1, với i=1,2,..,N, ghi 2 số nguyên dương A

i

và C

i

tương ứng là

khối lượng và giá trị sử dụng của đồ vật thứ I (0 < A

i

, C

i

< 256).

Kết quả: Ghi ra file văn bản BALO.OUT có cấu trúc:

Dòng đầu ghi tổng giá trị sử dụng lớn nhất tìm được.

21

Dòng 2 ghi chỉ số các đồ vật được xếp vào ba lô.

Ví dụ:

BALO.INP

BALO.OUT

7 20

3 9

8 23

23 4

29 34

12 4

1 2

8 6

40

1 2 6 7

*Hướng dẫn

Gọi L(i,t) là tổng giá trị lớn nhất khi được chọn i vật từ 1 đến i cho vào

balô với tổng khối lượng không vượt quá t.

L(n,m) sẽ là đáp số của bài toán (là giá trị lớn nhất có được nếu chọn n vật

và tổng khối lượng không vượt m).

Công thức tính L(i,t) như sau:

L(i,0)=0; L(0,t)=0.

L(i,t)=L(i–1,t) nếu t<A

i

.

L(i,t)=max(L(i–1,t), L(i–1,t–a

i

)+b

i

) nếu t ≥ a

i

. Trong đó: L(i–1,t) là giá trị có

được nếu không đưa vật i vào balô, L(i–1,t–a

i

)+b

i

là giá trị có được nếu chọn vật

i.

Ta có thể dùng một mảng 2 chiều để lưu bảng phương án, tuy nhiên dựa

trên nhận xét rằng để tính dòng i của bảng phương án chỉ cần dòng i–1, ta chỉ

cần dùng 2 mảng một chiều P và L có chỉ số từ 0 đến m để lưu 2 dòng đó. Đoạn

chương trình con tính bảng phương án như sau.

22

L[t] := 0; {với mọi t}

for I := 1 to n do begin

P:=L;

for t := 0 to m do

if t< L[t]:="P[t]" then> else L[t] := max(P[t],P[t –a[i]]);

end;

Nếu để ý kĩ bạn sẽ thấy rằng đoạn trình trên chỉ viết giống công thức

QHĐ chứ chưa tối ưu. Chẳng hạn đã có lệnh gán P:=L, sau đó lại có gán

L[t]:=P[t] với các giá trị t < a[i] là không cần thiết. Bạn đọc có thể tự cải tiến để

chương trình tối ưu hơn. Chi phí không gian của cách cài đặt trên là O(m) và chi

phí thời gian là O(n.m).

*Chương trình cài đặt:

program xep_do_vat;

uses crt;

const fi='balo.inp';

fo='balo.out';

max=10000;

type arrA=array[1..max]of longint;

arrB=array[0..max]of longint;

var f:text;

n,w,kq,luu:longint;

a,c :arrA;

d,gt:arrB;

truoc:arrA;

procedure init;

var i:longint;

23

begin

assign(f,fi);

reset(f);

readln(f,n,w);

for i:=1 to n do

readln(f,a[i],c[i]);

for i:=1 to w do

begin

d[i]:=0;

truoc[i]:=0;

gt[i]:=0;

end;

close(f);

kq:=0;

end;

procedure process;

var i,j:longint;

begin

d[0]:=1; gt[0]:=0;

for i:=1 to n do

begin

for j:=w downto a[i] do

if (d[j-a[i]]=1) then

if gt[j-a[i]]+c[i]>gt[j] then

begin

d[j]:=1;

24

gt[j]:=gt[j-a[i]]+c[i];

truoc[j]:=i;

if gt[j]>kq then

begin

kq:=gt[j];

luu:=j;

end;

end;

write(i,' ',truoc[87]);

readln;

end;

end;

procedure inkq;

var i :longint;

begin

assign(f,fo);

rewrite(f);

writeln(f,kq);

i:=truoc[luu];

while luu>a[i] do

begin

write(f,i,' ');

luu:=luu-a[i];

i:=truoc[luu];

end;

write(f,i);

25

close(f);

end;

BEGIN

init;

process;

inkq;

END.

26

Chương III:

Bài tập chọn lọc

Bài 5: Bố trí phòng họp;

Có n cuộc họp đánh số từ 1 đến n đăng ký làm việc tại một phòng hội

thảo. Cuộc họp i cần được bắt đầu tại thời điểm s

i

và kết thúc tại thời điểm f

i

.

Hỏi có thể bố trí phòng hội thảo phục vụ được nhiều nhất bao nhiêu cuộc họp

sao cho khoảng thời gian làm việc của hai cuộc họp được nhận phục vụ chỉ có

thể giao nhau tại đầu mút.

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

Dòng dầu tiên chứa số nguyên dương n (n <= 1000000)

Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên dương s

i

, f

i

(s

i

, f

i

<= 32000), i=1,2, …,n

Kết quả: Ghi ra file văn bản ACTIVITY.OUT

Dòng đầu tiên ghi số k là số lượng cuộc họp được chấp nhận phục vụ;

Mỗi dòng trong K dòng tiếp theo ghi chỉ số của một trong k cuộc họp được

chấp nhận

Ví dụ:

ACTIVITY.INP

ACTIVITY.OUT

5

1 3

2 4

1 6

3 5

7 9

3

1

4

5

27

* Hướng dẫn:

Sắp xếp các cuộc họp tăng dần theo thời điểm kết thúc (b

i

). Thế thì cuộc

họp i sẽ bố trí được sau cuộc họp j nếu và chỉ nếu j < i va` b

j

≤ a

i

. Yêu cầu bố trí

được nhiều cuộc họp nhất có thể đưa về việc tìm dãy các cuộc họp dài nhất

thoả mãn điều kiện trên

* Chương trình cài đặt:

program bo_tri_phong_hop;

uses crt;

const fi='activity.inp';

fo='activity.out';

max=1000000;

type arrA=array[1..max]of longint;

arrB=array[1..max,1..max]of longint;

var f:text;

n,luu,kq,dem:longint;

a,b,truoc,cs:arrA;

d,k:arrA;

procedure init;

var i:longint;

begin

assign(f,fi);

reset(f);

readln(f,n);

for i:=1 to n do

begin

readln(f,a[i],b[i]);

28

cs[i]:=i;

end;

close(f);

end;

procedure sap_xep;

var i,j,tg:longint;ok:boolean;

begin

for i:=1 to n-1 do

begin

ok:=true;

for j:=n downto i+1 do

if b[j]<b[j-1] then

begin

tg:=b[j];b[j]:=b[j -1];b[j-1]:=tg;

tg:=a[j];a[j]:=a[j-1];a[j-1]:=tg;

tg:=cs[j];cs[j]:=cs[j -1];cs[j-1]:=tg;

ok:=false;

end;

if ok then exit;

end;

end;

procedure process;

var i,j:longint;

begin

d[1]:=1;

for i:=1 to n do

29

truoc[i]:=i;

for i:=2 to n do

begin

d[i]:=1;

for j:=1 to n-1 do

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

if d[j]+1>d[i] then

begin

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

truoc[i]:=j;

end;

end;

kq:=-1;

for i:=1 to n do

if d[i]>kq then begin kq:=d[i];luu:=i;end;

while luu<>truoc[luu] do

begin

inc(dem);

k[dem]:=luu;

luu:=truoc[luu];

end;

inc(dem);

k[dem]:=luu;

end;

procedure inkq;

var i:longint;

30

begin

assign(f,fo);

rewrite(f);

writeln(f,kq);

for i:=dem downto 1 do

writeln(f,cs[k[i]]);

close(f);

end;

BEGIN

init;

sap_xep;

process;

inkq;

END.

Bài 6: Cho thuê máy tính;

Tại thời điểm 0, ông chủ cho thuê máy tính nhận được đơn đặt hàng thuê

sử dụng của N khách hàng. Các khách hàng đư ợc đánh số từ 1 đến N. Khách

hàng i cần sử dụng máy từ thời điểm di đến thời điểm ci (di và ci là các số

nguyên và 0 < di < ci < 1000000000), và s ẽ trả tiền sử dụng máy là pi (pi

nguyên, 0 < pi < 10000000);

Yêu cầu: Hãy xác định xem ông chủ cần nhận phục vụ những khách hàng

nào sao cho khoảng thời gian sử dụng máy tính của hai khách hàng được nhận

phục vụ bất kì không giao nhau và tổng tiền thu được từ phục vụ là lớn nhất.

Dữ liệu: vào từ file văn bản RENTING.INP. Dòng đầu tiên ghi số N (0 < N <

1000). Dòng thứ i trong N dòng tiếp theo ghi ba số di, ci, pi cách nhau bởi dấu

trống, i=1,2,..,N.

31

Kết quả: Ghi ra file văn bản RENTING.OUT. Dòng đầu tiên ghi hai số

nguyên dương theo thứ tự là số lượng khách hàng nhận được phục vụ và tổng

tiền thu được. Dòng tiếp theo ghi chỉ số của khách hàng được phục vụ.

Ví dụ:

RENTING.INP

RENTING.OUT

RENTING.INP

RENTING.OUT

3

150 500 150

1 200 100

400 800 80

2 180

2 3

4

400 821 800

200 513 500

100 325 200

600 900 600

2 1100

2 4

*Hướng dẫn:

Tương tự như bài toán 2, nếu sắp xếp các đơn đặt hàng theo thời điểm

kết thúc, ta sẽ đưa được bài toán 3 này về bài toán tìm dãy con có tổng lớn

nhất.

* Chương trình cài đặt:

program cho_thue_may_tinh;

uses crt;

const fi='renting.inp';

fo='renting.out';

max=1000;

type arrA=array[1..max]of int64;

arrB=array[1..max,1..max]of longint;

var f:text;

a,b,c:arrA;

n,kq,luu,dem:longint;

32

d,cs,truoc,k:arrA;

procedure init;

var i:longint;

begin

assign(f,fi);

reset(f);

readln(f,n);

for i:=1 to n do

begin

readln(f,a[i],b[i],c[i]);

cs[i]:=i;

end;

close(f);

end;

procedure sap_xep;

var i,j,tg:longint;ok:boolean;

begin

for i:=1 to n-1 do

begin

ok:=true;

for j:=n downto i+1 do

if b[j]<b[j-1] then

begin

tg:=b[j];b[j]:=b[j -1];b[j-1]:=tg;

tg:=a[j];a[j]:=a[j -1];a[j-1]:=tg;

tg:=cs[j];cs[j]:=cs [j-1];cs[j-1]:=tg;

33

tg:=c[j];c[j]:=c[j -1];c[j-1]:=tg;

ok:=false;

end;

if ok then exit;

end;

end;

procedure

process;

var i,j:longint;

begin

d[1]:=c[1];

for i:=1 to n do

truoc[i]:=i;

for i:=2 to n do

begin

d[i]:=c[i];

for j:=1 to n-1 do

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

if d[j]+c[i]>d[i] then

begin

d[i]:=d[j]+c[i];

truoc[i]:=j;

end;

end;

kq:=-1;

for i:=1 to n do

if d[i]>kq then begin kq:=d[i];luu:=i;end;

34

while luu<>truoc[luu] do

begin

inc(dem);

k[dem]:=luu;

luu:=truoc[luu];

end;

inc(dem);

k[dem]:=luu;

end;

procedure inkq;

var i:longint;

begin

assign(f,fo);

rewrite(f);

writeln(f,dem,' ',kq);

for i:=dem downto 1 do

write(f,cs[k[i]],' ');

close(f);

end;

BEGIN

init; sap_xep;

process;

inkq;

END.

Bài 7: Nối điểm

Trên hai đường thẳng song song L1 và L2 ngư ời ta đánh dấu trên mỗi

đường N điểm. Các điểm trên đường thẳng L1 được đánh số từ 1 đến N từ trái

35

sang phải, còn các điểm trên đường thẳng l2 được đánh số p1, p2, …, pN cũng

từ trái qua phải với p1, p2, …, pN là một hoán vị của 1, 2, …, N (Hình vẽ dưới

đây cho một ví dụ khi N=9):

Ta gọi các số gán cho các điểm là số hiệu của chúng. Cho phép nối hai

điểm trên hai đường thẳng có cùng số hiệu.

Yêu cầu tìm cách nối được nhiều cặp điểm nhất với điều kiện các đoạn

nối không được cắt nhau.

Dữ liệu: vào từ file văn bản WIRE.INP có cấu trúc như sau:

Dòng đầu tiên chứa số nguyên dương N (N < 1000);

Dòng thứ hai chứa các số nguyên p1, p2, …, pN cách nhau b ởi dấu trắng;

Kết quả: Ghi ra file văn bản WIRE.OUT có cấu trúc:

Dòng đầu tiên chứa số k là số lượng các đoạn nối tìm được;

Dòng tiếp theo chứa k số hiệu của các đầu mút của các đoạn nối được ghi

theo thứ tự tăng dần.

Ví dụ:

WIRE.INP

WIRE.OUT

9

2 5 3 8 7 4 6 9 1

5

3 4 6 9

*Hướng dẫn:

Đây chính là bài toán 1: Tìm dãy con không gi ảm dài nhất

* Chương trình cài đặt:

program day_con;

uses crt;

36

const fi='wires.inp';

fo='wires.out';

max=1000;

type arrA=array[0..max]of longint;

arrB=array[1..max,1..max]of longint;

var f:text;

a:arrA;

n,kq,luu,dem:longint;

d,truoc,k:arrA;

procedure init;

var i:longint;

begin

assign(f,fi);

reset(f);

readln(f,n);

for i:=1 to n do

read(f,a[i]);

close(f);

end;

procedure process;

var i,j:longint;

begin

for i:=1 to n do

truoc[i]:=i;

d[1]:=1;

for i:=1 to n do

37

begin

d[i]:=1;

for j:=1 to i-1 do

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

if d[j]+1>d[i] then

begin

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

truoc[i]:=j;

end;

end;

kq:=0;

for i:=1 to n do

if d[i]>kq then begin kq:=d[i];luu:=i;end;

dem:=0;

while truoc[luu]<>luu do

begin

inc(dem);

k[dem]:=luu;

luu:=truoc[luu];

end;

inc(dem);

k[dem]:=luu;

end;

procedure inkq;

var i:longint;

begin

38

assign(f,fo);

rewrite(f);

writeln(f,kq);

for i:=dem downto 1 do

write(f,a[k[i]],' ');

close(f);

end;

BEGIN

init;

process; inkq;

END.

Bài 8: Dãy con đổi chiều, đối dấu dài nhất;

Cho dãy a

1

, a

2

,... a

n

. Hãy tìm dãy con đổi chiều dài nhất của dãy đó. Dãy

con con đổi dấu a

i1

,a

i2

,... a

ik

phải thoả mãn các điều kiện sau:

a

i1

< a

i2

> a

i3

<... hoặc a

i1

> a

i2

< a

i3

>... các chỉ số phải cách nhau ít nhất L: i

2

- i

1

≥ L, i

3

-i

2

≥ L... chênh lệch giữa 2 phần tử liên tiếp nhỏ hơn U: |a

i1

- a

i2

| ≤ U,

|a

i2

- a

i3

| ≤ U...

Ví dụ: Cho dãy 10 phần tử: -1, 3, -4, 13, 6, 9, -2, 12, -3, 15 và L=2 và U=3

Có 1 dãy con đổi chiều dài nhất là: -1, -4, -2, -3

Dữ liệu: Vào từ file văn bản DOICHIEU.INP có cấu trúc như sau:

Dòng đầu tiên ghi 3 số nguyên dương n, L, U (n <10

5

; 1<L<n-1; 0 < U <

1000);

Các dòng tiếp theo ghi n số của dãy a; (|a

i

| <= 32000);

Kết quả: Ghi ra file văn bản DOICHIEU.OUT có cấu trúc như sau:

Dòng đầu là độ dài dãy con đổi chiều dài nhất tìm được;

Chỉ số các phần tử của dãy con tìm được trong dãy ban đầu;

39

Ví dụ:

DOICHIEU.INP

DOICHIEU.OUT

10 2 3

-1 3 -4 13 6 9 -2 12 -3 15

4

1 3 7 9

* Hướng dẫn:

Gọi L(i) là số phần tử của dãy con đổi dấu có phần tử cuối cùng là a

i

và

phần tử cuối cùng lớn hơn phần tử đứng trước. Tương tự, P(i) là số phần tử

của dãy con đổi dấu có phần tử cuối cùng là a

i

và phần tử cuối cùng nhỏ hơn

phần tử đứng trước. Ta dễ dàng suy ra:

L(i) = max(1, P(j)+1): j ≤ i - L và a

i

- U ≤ a

j

< a

i

.

P(i) = max(1, L(j)+1): j ≤ i - L và a

i

< a

j

≤ a

i

+ U.

* Chương trình cài đặt:

program day_con_doi_chieu_dai_nhat;

uses crt;

const fi='doichieu.inp';

fo='doichieu.out';

max=100000;

type arrA=array[1..max]of longint;

arrB=array[1..max,1..max]of longint;

var f:text;

n,l,u,luu,kq,cs,dem:longint;

a:arrA;

d1,d2,truoc1,truoc2,k:arrA;

procedure init;

var i:longint;

begin

40

assign(f,fi);

reset(f);

readln(f,n,l,u);

for i:=1 to n do

begin

read(f,a[i]);

truoc1[i]:=i;

truoc2[i]:=i;

end;

close(f);

end;

procedure process;

var i,j:longint;ok:boolean;

begin

d1[1]:=1;

d2[1]:=1;

for i:=2 to n do

begin

d1[i]:=1;

for j:=1 to i-l do

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

if abs(a[i]-a[j])<=U then

if d2[j]+1>d1[i] then

begin

d1[i]:=d2[j]+1;

truoc1[i]:=j;

41

end;

d2[i]:=1;

for j:=1 to i-l do

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

if abs(a[i]-a[j])<=U then

if d1[j]+1>d2[i] then

begin

d2[i]:=d1[j]+1;

truoc2[i]:=j;

end;

end;

kq:=-1;

for i:=1 to n do

begin

if d1[i]>kq then begin kq:=d1[i];cs:=1;luu:=i;end;

if d2[i]>kq then begin kq:=d2[i];cs:=2;luu:=i;end;

end;

end;

procedure

truy_xuat;

var ok:boolean;

begin

ok:=false;

dem:=0;

repeat

inc(dem);

k[dem]:=luu;

42

if cs=1 then

begin

if luu=truoc1[luu]then

exit

else

begin

luu:=truoc1[luu];

cs:=2;

end;

end

else

begin

if luu=truoc2[luu] then

exit

else

begin

luu:=truoc2[luu];

cs:=1;

end;

end;

until ok;

end;

procedure inkq;

var i:longint;

begin

assign(f,fo);

43

rewrite(f);

writeln(f,kq);

for i:=dem downto 1 do

write(f,k[i],' ');

close(f);

end;

BEGIN

init; process;

truy_xuat; inkq;

END.

Bài 9: Số phép biến đổi ít nhất

Cho 2 xâu X,Y. Có 3 phép biến đổi với xâu X: chèn 1 kí tự, thay thế một kí

tự hoặc xoá một kí tự. Hãy tìm số ít nhất các phép biến đổi để biến xâu X

thành

xâu

Y.

Ví dụ: Cho xâu X=’kitten’ và Y=’sitting’ thì c ần ít nhất là 3 phép biến đổi

Dữ liệu: Vào từ file văn bản BIENDOI.INP có cấu trúc như sau:

Dòng 1 chứa xâu X

Dòng 2 chứa xâu Y

(Mỗi xâu có không quá 200 kí tự)

Kết quả: Ghi ra file văn bản BIENDOI.OUT ghi 1 số là số phép biến đổi ít

nhất tìm được;

Ví dụ:

BIENDOI.INP

BIENDOI.OUT

kitten

sitting

3

* Hướng dẫn:

44

Gọi F(i,j) là số phép biến đổi ít nhất để biến xâu X(i) gồm i kí tự phần đầu

của X (X(i)= X[1..i]) thành xâu Y(j) g ồm j kí tự phần đầu của Y (Y(j) =Y[1..j]). Dễ

thấy F(0,j)=j và F(i,0)=i.

Nếu X[i]=Y[j] thì ta chỉ phải biến đổi xâu X(i-1) thành xâu Y(j-1). Do đó

F(i,j)=F(i-1,j-1).

Ngược lại, ta có 3 cách biến đổi:

- Xoá kí tự X[i] và biến đổi xâu X(i-1) thành Y(j). Khi đó F(i,j)=F(i-1,j)+1.

- Thay thế X[i] bởi Y[j] và biến đổi X(i-1) thành Y(j-1). Khi đó F(i,j)=F(i-

1,j-1)+1.

- Chèn Y[j] vào X(i) và biến đổi X(i) thành Y(j-1). Khi đó F(i,j)=F(i,j-1)+1.

Tổng kết lại, ta có công thức QHĐ:

F(0,j)=j

F(i,0)=i

F(i,j) =F(i - 1,j - 1) nếu X[i] = Y[j].

F(i,j) = min(F(i - 1,j),F(i,j - 1),F(i - 1,j - 1))+1 nếu X[i] ≠ Y[j].

*Chương trình cài đặt:

program bien_doi_xau;

uses crt;

const fi='biendoi.inp';

fo='biendoi.out';

max=100;

type arrA=array[1..max]of char;

arrB=array[0..max,0..max]of longint;

var f:text;

m,n:longint;

d:arrB;

45

a,b:arrA;

procedure init;

begin

assign(f,fi);

reset(f);

m:=0;

while not eoln(f) do

begin

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

end;

readln(f);

n:=0;

while not eof(f) do

begin

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

end;

close(f);

end;

function min3so(x,y,z:longint):longint;

var tam:longint;

begin

if x<y then tam:=x

else tam:=y;

if z<tam then tam:=z;

min3so:=tam;

end;

46

procedure

process;

var i,j:longint;

begin

for i:=1 to m do d[i,0]:=i;

for j:=1 to n do d[0,j]:=j;

for i:=1 to m do

for j:=1 to n do

begin

if a[i]=b[j] then d[i,j]:=d[i -1,j-1]

else

d[i,j]:=min3so(d[i-1,j-1],d[i,j-1],d[i-1,j])+1;

end;

end;

procedure inkq;

begin

assign(f,fo);

rewrite(f);

writeln(f,d[m,n]);

close(f);

end;

BEGIN

init;

process;

inkq;

END.

47

Bài 10: Xâu đối xứng;

Một xâu gọi là xâu đối xứng (palindrom) nếu xâu đó đọc từ trái sang phải

hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần

thêm vào S để S trở thành xâu đối xứng.

Ví dụ: Cho xâu S=’abcda’ thì số kí tự ít nhất cần chèn thêm là 2

Dữ liệu: Vào từ file văn bản XDX.INP là 1 xâu S có không quá 500 kí t ự)

Kết quả: Ghi ra file văn bản XDX.OUT là số lượng kí tự ít nhất cần thêm;

Ví dụ:

XDX.INP

XDX.OUT

abcda

2

*Hướng dẫn:

Gọi L(i,j) là số kí tự ít nhất cần thêm vào xâu con S[i..j] của S để xâu đó trở

thành đối xứng. Đáp số của bài toán sẽ là L(1,n) với n là số kí tự của S. Ta có

công thức sau để tính L(i,j):

L(i,i)=0.

L(i,j)=L(i+1,j - 1) nếu S[i]=S[j]

L(i,j)=max(L(i+1,j), L(i,j - 1)) nếu S[i] ≠ S[j] ;

Ta có thuật toán đơn giản hơn như sau:

Gọi P là xâu đảo của S và T là xâu con chung dài nh ất của S và P. Khi đó

các kí tự của S không thuộc T cũng là các kí tự cần thêm vào để S trở thành đối

xứng. Đáp số của bài toán sẽ là n - k, với k là độ dài của T. Ví dụ:

S=<b>edbabcd, xâu đảo của S là P=<b>dcbabde. Xâu con chung dài nh ất của S

và P là T=<b>dbabd. Như v ậy cần thêm 2 kí tự là e và c vào để S trở thành xâu

đối xứng;

*Chương trình cài đặt:

program xau_doi_xung;

48

uses crt;

const fi='palin.inp';

fo='palin.out';

max=5000;

type arrA=array[1..max]of char;

arrB=array[1..max,1..max]of longint;

var a:arrA;

l:arrB;

f:text;

n:integer;

procedure init;

var i:integer;

begin

assign(f,fi);

reset(f);

readln(f,n);

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

close(f);

end;

function min2so(x,y:longint):longint;

begin

if x>y then min2so:=y

else min2so:=x;

end;

procedure process;

var i,j:longint;

49

begin

for i:=1 to n do

l[i,i]:=0;

for i:=1 to n-1 do

for j:=1 to n-i do

begin

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

begin

if i=1 then l[j,j+i]:=0

else

l[j,j+i]:=l[j+1,j+i -1];

end

else

l[j,j+i]:=min2so(l[j+1,j+i],l[j,j+i-1])+1;

end;

end;

procedure inkq;

begin

assign(f,fo);

rewrite(f);

writeln(f,l[1,n]);

close(f);

end;

BEGIN

init;

process;

50

inkq;

END.

Bài 11: Bài toán chia kẹo

Có N gói kẹo, gói thứ i có A

i

cái kẹo. Không được bóc bất kỳ một gói kẹo

nào, cần chia N gói kẹo thành hai phần sao cho độ chênh lệch số kẹo giữa hai

gói là ít nhất.

Dữ liệu:Vào từ file văn bản "chiakeo.inp" có dạng :

- Dòng đầu tiên là số N (N<=100);

- Dòng thứ hai là N số A

i

(i=1, 2,.., N; A

i

<=100).

Kết quả: Ghi ra file văn bản "chiakeo.out" có dạng:

- Dòng đầu là độ chênh lệch nhỏ nhất giữa hai phần có thể được.

- Dòng thứ hai là các chỉ số của của các phần tử trong dãy a thuộc phần

1 ;

- Dòng thứ ba là các chỉ số của các phần tử trong dãy a thuộc phần 2 ;

Ví dụ:

CHIAKEO.INP

CHIAKEO.OUT

8
19 5 20 13 16 20 18 2

1 56 57
3 5 6
1 2 4 7 8

*Hướng dẫn:

Gọi T là tổng số kẹo của n gói. Chúng ta cần tìm số S lớn nhất thoả mãn:

S ≤ T/2.

Có một dãy con của dãy a có tổng bằng S. Khi đó sẽ có cách chia với

chênh lệch 2 phần là T- 2S là nhỏ nhất và dãy con có tổng bằng S ở trên gồm

các phần tử là các gói kẹo thuộc phần thứ nhất. Phần thứ hai là các gói kẹo

còn lại.

* Chương trình cài đặt:

program chia_keo;

51

uses crt;

const fi='chiakeo.inp';

fo='chiakeo.out';

max=100;

var a:array[1..max]of integer;

n:integer;

t,k:integer;

s:array[0..max,0..10000]of integer;

f:text;

t1,lech:integer;

cx:array[1..max]of boolean;

procedure init;

var i:integer;

begin

assign(f,fi);

reset(f);

readln(f,n);

for i:=1 to n do

read(f,a[i]);

close(f);

k:=0;

for i:=1 to n dok:=k+a[i];

t:=k div 2;

for i:=1 to n do s[i,0]:=1;

for i:=1 to t do s[0,i]:=0;

for i:=1 to n do cx[i]:=true;

52

end;

procedure process;

var i,j:integer;

begin

for i:=1 to n do

for j:=1 to t do

begin

s[i,j]:=0;

if s[i-1,j]=1 then s[i,j]:=1;

if j>=a[i] then

if s[i-1,j-a[i]]=1 then s[i,j]:=1;

end;

end;

procedure xu_li;

var i,j:integer;

begin

for i:=t downto 1 do

begin

for j:=1 to n do

if s[j,i]=1 then

begin

t1:=i;

lech:=k-2*i;

exit;

end;

end;

53

end;

procedure truy_ket_qua;

var tam,i,t2:integer;

begin

tam:=t1;

t2:=n;

repeat

for i:=1 to t2 do

if s[i,tam]=1 then

begin

t2:=i;

tam:=tam-a[i];

cx[i]:=false;

break;

end;

until (tam=0);

end;

procedure inkq;

var i:integer;

begin

assign(f,fo);

rewrite(f);

writeln(f,lech,' ',t1,' ',k-t1);

for i:=1 to n do if cx[i]=false then write(f,i,' ');

writeln(f);

for i:=1 to n do if cx[i]=true then write(f,i,' ');

54

close(f);

end;

BEGIN

init;

process;

xu_li;

truy_ket_qua;

inkq;

END.

Bài 12: Mua cá theo lýợng (Olympic Balkan 2000) ;

Người đánh cá Clement bắt được n con cá, khối lượng mỗi con là a

i

, đem

bán ngoài chợ. Ở chợ cá, người ta không mua cá theo t ừng con mà mua theo

một lượng nào đó và một con cá bất kì không được cắt ra. Chẳng hạn 3 kg,

5kg...

Ví dụ: có 3 con cá, khối lượng lần lượt là: 3, 2, 4. Mua lượng 6 kg sẽ phải

lấy con cá thứ 2 và và thứ 3. Mua lượng 3 kg thì lấy con thứ nhất. Không thể

mua lượng 8 kg.

Nếu bạn là người đầu tiên mua cá, có bao nhiêu lượng bạn có thể chọn?

Dữ liệu vào: Đọc từ file văn bản MARKET.INP có cấu trúc:

-

Dòng đầu tiên ghi số nguyên n (n <= 10

4

) ;

-

Các dòng tiếp theo ghi các giá trị a

i

(i=1,2,..,n)

Kết quả ra: Ghi ra file văn bản MARKET.OUT ghi số l là số lượng tìm được.

Ví dụ:

MARKET.INP

MARKET.OUT

3
3 2 4

7

55

* Hướng dẫn:

Thực chất bài toán là tìm các số S mà có một dãy con của dãy a có tổng

bằng S. Ta có thể dùng phương pháp đánh dấu của bài chia kẹo ở trên rồi đếm

các giá trị t mà L[t]=1.

* Chương trình cài đặt:

program so_ca;

uses crt;

const fi='market.inp';

fo='market.out';

maxn=10000;

max=1000000;

type arrA=array[1..maxn]of longint;

arrB=array[0..max]of longint;

var f:text;

a:arrA;

s,dem,n:longint;

d:arrB;

procedure init;

var i:longint;

begin

assign(f,fi);

reset(f);

readln(f,n);

s:=0;

for i:=1 to n do

begin

56

read(f,a[i]);

s:=s+a[i];

end;

close(f);

end;

procedure process;

var i,j:longint;

begin

for i:=1 to s do

d[i]:=0;

d[0]:=1;

for i:=1 to n do

for j:=s downto a[i] do

begin

if (d[j]=0) and (d[j-a[i]]=1) then

begin

d[j]:=1;

inc(dem);

end;

end;

end;

procedure inkq;

begin

assign(f,fo);

rewrite(f);

writeln(f,dem);

57

close(f);

end;

Bài 13: Điền dấu hỏi vào biểu thức

Cho n số tự nhiên a

1

,a

2

,...,a

n

. Ban đầu các số được đặt liên tiếp theo đúng

thứ tự cách nhau bởi dấu '?': a

1

?a

2

?...?a

n

. Cho trước số nguyên S, có cách nào

thay các dấu '?' bằng dấu + hay dấu - để được một biểu thức số học cho giá trị

là S không?

Dữ liệu vào: Đọc từ file văn bản DAUHOI.INP có cấu trúc như sau:

Dòng đầu ghi 2 số nguyên dương n và S (n <=10

4

, S<=10

5

);

Các dòng tiếp theo ghi n giá trị a

1

, a

2

, …, a

n

Kết quả ra: Ghi ra file văn bản DAUHOI.OUT có cấu trúc như sau:

Dòng đầu ghi 0 hoặc 1 tương ứng là không có cách thay các d ấu hỏi hoặc

có tồn tại cách thay dấu hỏi bằng dấu + hay - để giá trị của biểu thức bằng S;

Nếu dòng 1 ghi số 1 thì dòng tiếp theo ghi 1 cách thay dấu hỏi bởi phép

toán + hoặc - tìm được (chỉ cần ghi các dấu theo thứ tự từ trái sang phải)

Ví dụ:

DAUHOI.INP DAUHOI.OUT

5 20

4 5 6 7 8

1

-+++

*Hướng dẫn:

Đặt L(i,t)=1 nếu có thể điền dấu vào i số đầu tiên và cho kết quả bằng t.

Ta có công thức sau để tính L:

L(1,a[1]) =1.

L(i,t)=1 nếu L(i - 1,t+a[i])=1 hoặc L(i - 1,t - a[i])=1.

Nếu L(n,S)=1 thì câu trả lời của bài toán là có. Khi cài đặt, có thể dùng

một mảng 2 chiều (lưu toàn bộ bảng phương án) hoặc 2 mảng một chiều (để

58

lưu dòng i và dòng i - 1). Chú ý là chỉ số theo t của các mảng phải có cả phần âm

(tức là từ - T đến T, với T là tổng của n số), vì trong bài này chúng ta dùng c ả

dấu - nên có thể tạo ra các tổng âm.

Bài này có một biến thể là đặt dấu sao cho kết quả là một số chia hết cho

k. Ta có thuật giải tương tự bài toán trên bằng cách thay các phép cộng, trừ

bằng các hép cộng và trừ theo môđun k và dùng mảng đánh dấu với các giá trị

từ 0 đến k - 1 (là các số dư có thể có khi chia cho k). Đáp số của bài toán là

L(n,0).

* Chương trình cài đặt:

program dau_hoi;

uses crt;

const fi='daudoi.inp';

fo='dauhoi.out';

max=10000;

maxs=100000;

type arrA=array[1..max]of longint;

arrB=array[0..maxs]of longint;

var f:text;

n,s,tong:longint;

a:arrA;

d:arrB;

ok:boolean;

truoc:arrA;

co:array[1..max]of boolean;

procedure init;

59

var

i:longint;

begin

assign(f,fi);

reset(f);

readln(f,n,s);

tong:=0;

for i:=1 to s do

begin

read(f,a[i]);

tong:=tong+a[i];

co[i]:=true;

end;

ok:=true;

if tong<s then ok:=false;

tong:=tong-s;

if tong mod 2 <>0 then ok:=false

else tong:=tong div 2;

close(f);

end;

procedure process;

var i,j:longint;

begin

for i:=1 to tong do

d[i]:=0;

d[0]:=1;

60

for i:=1 to n do

for j:=tong downto a[i] do

begin

if (d[j]=0) and (d[j-a[i]]=1) then

begin

d[j]:=1;

truoc[j]:=i;

end;

if d[tong]<>0 then exit;

end;

end;

procedure inkq;

var luu,i:longint;

begin

assign(f,fo);

rewrite(f);

if (d[tong]=0) or (truoc[tong]=1) then

ok:=false

else

begin

s:=tong;luu:=truoc[s];

while s<>a[luu] do

begin

co[luu]:=false;

s:=s-a[luu];

luu:=truoc[s];

61

end;

co[luu]:=false;

end;

if ok then

begin

writeln(f,'1');

for i:=2 to n do

begin

if co[i] then write(f,'+')

else write(f,'-');

end;

end

else write(f,'0');

close(f);

end;

BEGIN init;

if ok then process; inkq;

END.

Bài 14: Chia thành hai nhóm có tích lớn nhất (ACM 10690)

Cho n số nguyên. Hãy chia chúng thành 2 nhóm sao cho tích c ủa tổng 2

nhóm là lớn nhất.

Dữ liệu vào: Đọc từ file văn bản EXPRESSION.INP có cấu trúc như sau:

-

Dòng đầu ghi 1 số nguyên dương n (n <=10

4

);

-

Các dòng tiếp theo ghi n giá trị a

1

, a

2

, …, a

n

Kết quả ra: Ghi ra file văn bản EXPRESSION.OUT có cấu trúc như sau:

-

Giá trị S là tích lớn nhất của tổng 2 nhóm t ìm được;

62

Ví dụ:

EXPRESSION.INP

EXPRESSION.OUT

5

1 2 3 4 5

56

*Hướng dẫn:

Gọi T là tổng n số nguyên đó. Giả sử ta chia dãy thành 2 nhóm, gọi S là

tổng của một nhóm, tổng nhóm còn lại là T - S và tích của tổng 2 nhóm là S*(T -

S). Bằng phương pháp đánh dấu ta xác định được mọi số S là tổng của một

nhóm (như bài Market) và t ìm số S sao cho S*(T - S) đạt max.

*Chương trình cài đặt:

uses crt;

const fi='expression.inp';

fo='expression.out';

max=10000;

maxs=100000;

type arrA=array[1..max]of longint;

arrB=array[0..maxs]of longint;

var f:text;

n,s,tong:longint;

a:arrA;

d:arrB;

ok:boolean;

procedure init;

var i:longint;

63

begin

assign(f,fi);

reset(f);

readln(f,n);

for i:=1 to n do

begin

read(f,a[i]);

tong:=tong+a[i];

end;

close(f);

end;

procedure process;

var i,j:longint;

begin

for i:=1 to s do

d[i]:=0;

d[0]:=1;

for i:=1 to n do

for j:=s downto a[i] do

begin

if (d[j]=0) and (d[j-a[i]]=1) then

d[j]:=1;

if d[s]<>0 then begin ok:=true;exit;end;

end;

end;

procedure xu_li;

64

begin

s:=tong div 2 ;

while not ok do process;

end;

procedure inkq;

begin

assign(f,fo);

rewrite(f);

if n<>1 then

write(f,(s+1)*(tong-s-1))

else writeln(f,'0');

close(f);

end;

BEGIN

init;

if n<>1 then xu_li;

inkq;

END.

Bài 15: Bài toán mua bán hàng

Có một người đi mua hàng, anh ta có N đồng tiền d

1

, d

2

,.., d

N

. Người bán

hàng có M đồng tiền b

1

, b

2

,.., b

m

. Anh ta muốn mua một mặt hàng với giá trị W.

Hỏi cuộc mua bán có thể diễn ra được không?

Giới hạn: M, N<=100 và d

i

, b

j

<=100.

Dữ liệu vào đọc từ file văn bản MUABAN.INP có cấu trúc như sau:

-

Dòng đầu ghi 3 số nguyên dương N, M, W

-

Dòng thứ 2 ghi N số d

1

, d

2

,.., d

N

;

65

-

Dòng thứ 3 ghi M số b

1

, b

2

,.., b

m

;

Kết quả ghi ra file văn bản MUABAN.OUT có cấu trúc như sau:

-

Dòng đầu ghi số 0 hoặc 1 tương ứng là không thể diễn ra cuộc mua

bán hoặc có thể diễn ra cuộc mua bán;

-

Nếu dòng đầu là 1 thì dòng 2 ghi chỉ số các đồng tiền mà người mua

hàng đã sử dụng để trao đổi, còn dòng 3 ghi chỉ số các đồng tiền mà

người bán hàng đã sử dụng để trao đổi;

Ví dụ:

MUABAN.INP

MUABAN.OUT

MUABAN.INP

MUABAN.OUT

6 10 30

5 7 6 11 2 26

1 2 3 5 6 7

8 9 10

1

1 2 3 4 5

1

4 3 30

6 11 2 26

10 20 30

0

* Chương trình cài đặt:

program mua_ban_hang;

uses crt;

const fi='muaban.inp';

fo='muaban.out';

max=100;

maxs=10000000;

type arrA=array[1..max]of longint;

arrB=array[0..maxs]of longint;

var f:text;

a,b:arrA;

d:arrB;

n,m,w,tong,luu1,luu2,s,v:longint;

ok1,ok2,ok:boolean;

66

truoc1,truoc2:arrA;

procedure init;

var i:longint;

begin

assign(f,fi);

reset(f);

readln(f,n,m,w);

tong:=0;

for i:=1 to n do

begin

read(f,a[i]);

tong:=tong+a[i];

end;

readln(f);

for i:=1 to m do

read(f,b[i]);

close(f);

end;

procedure process1;

var i,j:longint;

begin

for i:=1 to s do

begin

d[i]:=0;

truoc1[i]:=0;

end;

67

d[0]:=1;

for i:=1 to n do

for j:=s downto a[i] do

begin

if (d[j]=0) and (d[j-a[i]]=1) then

begin

d[j]:=1;

truoc1[j]:=i;

end;

if d[s]<>0 then begin ok1:=true;exit;end;

end;

end;

procedure process2;

var i,j:longint;

begin

d[0]:=1;

for i:=1 to v do

begin

d[i]:=0;

truoc2[i]:=0;

end;

for i:=1 to m do

for j:=v downto b[i] do

begin

if (d[j]=0) and (d[j-b[i]]=1) then

begin

68

d[j]:=1;

truoc2[j]:=i;

end;

if d[v]<>0 then begin ok2:=true; exit;end;

end;

end;

procedure xu_li;

begin

ok:=false;

for s:=w to tong do

begin

ok1:=false;

process1;

if ok1 then

begin

ok2:=false;

v:=s-w;

if v=0 then ok2:=true

else

process2;

end;

if ok1 and ok2 then

begin

luu1:=s;

luu2:=v;

ok:=true;

69

break;

end;

end;

end;

procedure inkq;

var i:longint;

begin

assign(f,fo);

rewrite(f);

if ok then

begin

writeln(f,'1');

i:=truoc1[luu1];

while luu1<>a[i] do

begin

write(f,i,' ');

luu1:=luu1-a[i];

i:=truoc1[luu1];

end;

writeln(f,i);

if luu2<>0 then

begin

i:=truoc2[luu2];

while luu2<>b[i] do

begin

write(f,i,' ');

70

luu2:=luu2-b[i];

i:=truoc2[luu2];

end;

write(f,i);

end;

end

else writeln(f,'0');

close(f);

end;

BEGIN

init;

xu_li;

inkq;

END.

Bài 16: Lịch thuê nhân công

Có một dự án kéo dài trong T tháng và ngư ời quản lý cần phải lập lịch sử

dụng công nhân trong dự án, anh ta biết số công nhân tối thiểu cần trong mỗi

tháng. Mỗi khi thuê hay sa thải một công nhân thì đều phải mất một chi phí

xác định, mỗi công nhân được thuê sẽ vẫn nhận được lương tháng ngay cả khi

không sử dụng anh ta làm việc.

Với mỗi công nhân, người quản lý biết chi phí thuê, chi phí sa thải và tiền

lương phải trả cho công nhân đó trong 1 tháng. Và bài toán đ ặt ra như sau: Cần

phải thuê hay sa thải bao nhiêu công nhân mỗi tháng để tổng chi phí dành cho

nhân công của dự án là nhỏ nhất, tức là giảm tối đa chi phí của dự án.

Dữ liệu vào: Đọc từ file văn bản EMPLOY.IN có cấu trúc như sau:

- Dòng đầu ghi T là số tháng diễn ra dự án (T=<100).

71

- Dòng thứ hai ghi 3 số lần lượt là chi phí thuê, lương tháng, chi phí sa th ải

mỗi công nhân.

- Dòng cuối cùng là T số nguyên dương, số thứ i cho biết số công nhân tối

thiểu cần cho tháng thứ i, các giá trị số không quá 150.

Kết quả ra: Ghi ra file văn bản EMPLOY.OUT theo định dạng:

- Dòng thứ nhất ghi tổng chi phí nhỏ nhất tìm được.

- Dòng thứ hai ghi T số, số thứ i là số công nhân hoạt động trong dự án tại

tháng thứ i.

Ví dụ: về file dữ liệu vào và file kết quả ra:

EMPLOY.IN

EMPLOY.OUT

3

4 5 6

10 9 11

265

10 10 11

* Hướng dẫn:

Đề bài này hơi rắc rối khó hiểu một chút vì vậy cần phải đọc kỹ, nắm

chắc. Rõ ràng việc thuê thêm hay sa thải công nhân đều phải chịu phí tổn nên

thấy: để đảm bảo chi phí ít nhất cho việc thuê nhân công trong cả dự án thì số

công nhân đang thuê trong một tháng không nhất thiết phải là số công nhân tối

thiểu cần cho tháng đấy. Ví dụ, phí tổn để thuê cũng như sa thải công nhân rất

lớn thì không dại gì ta lại thường xuyên thuê rồi lại sa thải người trong từng

tháng, tốt nhất nên giữ họvà trả lương (dù họ không làm gì). Nhiệm vụ của

chúng ta trong mỗi tháng phải quyết định có bao nhiêu công nhân trong biên

chế thuê, nghĩa là phải quyết định xem cần thuê hay cần sa thải bao nhiêu công

nhân trong biên chế của tháng trước. Nếu gọi T_max là số công nhân của tháng

cần nhiều người nhất thì rõ ràng số công nhân trong biên chế thuê của một

tháng bất kỳ trong dự án không bao giờ vượt quá T_max. Xét một tháng nào đó,

72

biết rằng không nên sử dụng quá T_max người và cũng không được phép sử

dụng ít hơn số người tối thiểu cần cho tháng đấy, nhưng phải chọn giá trị nào

trong khoảng giới hạn này. Đến đây nếu các giá trị của T và T_max là nhỏ thì có

thể duyệt tìm ra kết quả tối ưu nhưng do cácgiá trị này lại có thể khá lớn nên

buộc phải tìm cách khác hiệu quả hơn.

Lập mảng Scn[1..T], Scn[i] cho biết số công nhân tối thiểu cần cho tháng

thứ i, i=1..T(mảng này nhập vào từ file input). Lập thêm mảng C[T,T_max]

trong đó C[i,j] cho biết chi phí tối thiểu của i tháng đầu tiên của dự án nếu tại

tháng thứ i có j công nhân trong biên chế thuê (i=1..T, =1..T_max). Thấy là giá

trị C[i,j] cóthể xác định thông qua các giá trị C tại tháng i-1 (là tháng trước):

C[i,j] = Min{C[i-1,k] + chi phí để từ k người thành j người }

( i=1..T;j=Scn[i]..T_max; k=Scn[i -1]..T_max)

Bài toán đã đơn giản hơn nhiều khi có được công thức truy hồi và vì độ

phức tạp tính toán không lớn nên chắc chắn chương trình sẽ ngắn gọn, cho kết

quả tối ưu trong thời gianrất ngắn. Kết quả tối ưu cuối cùng là:

Kq = Min{C[T,j]+ chi phí sa thải j người}

(j=Scn[T]..T_max)

Để có thể đưa ra kết quả đầy đủ(số công nhân sử dụng mỗi tháng) thì cần

thêm mảng hai chiều Pre, trong đóPre[i,j] := k, v ới i=1..T; j=Scn[i]..T_max; k

thoả mãn tổng (C[i-1,k] + chi phí để từ k người thành j người) nhỏ nhất. Việc

lần ngược tìm kết quả trong mảngPre không khó.

Bài 17: Cắt hình chữ nhật

Ta cần cắt một hình chữ nhật có kích thước M x N (M, N nguyên dương

không lớn hơn 100) thành một số ít nhất các hình vuông có kích thước nguyên

dương và có cạnh song song với cạnh của hình chữ nhật ban đầu. Biết rằng khi

73

cắt một hình chữ nhật bất kỳ chỉ cắt được theo 1 phương song song với một

trong các các cạnh của hình chữ nhật đó.

Dữ liệu vào: Đọc từ file văn bản CUT.INP có một dòng ghi 2 số M, N.

Kết quả ra: Ghi ra file CUT.OUT có cấu trúc như sau:

Dòng thứ nhất ghi số K là số hình vuông ít nhất cắt ra.

Dòng thứ 2 ghi kích thước của K hình vuông cắt ra được, mỗi số cách nhau

1 dấu cách.

Ví dụ:

CUT.INP CUT.OUT

5 6

5

2 2 2 3 3

Mô tả trên hình vẽ: (Số ghi trong hình vuông cho biết kích thước của hình

vuông đó)

*Hướng dẫn:

+ Nếu M = 1 thì cắt được ít nhất bao nhiêu hình vuông thoả mãn?

+ Nếu N = 1 thì cắt được ít nhất bao nhiêu hình vuông thoả mãn?

+ Nếu gọi F[i,j] là số hình vuông ít nhất cắt ra từ hình chữ nhật kích thước

i, j (với 1 < i < M; 1 < j < N) thì công thức QHĐ được xây dựng như thế nào?

Bài toán con cơ sở: F[1,j] := j với mọi j; F[i,1] := i với mọi i

Công thức QHĐ:

Với i := 2, .., m

Với j := 2, .., n

Nếu i = j thì F[i,i] := 1

2

2

2

3

3

74

Trái lại

t1 := min{F[k,j] + F[i-k, j]} với k = 1,2, …, i div 2;

t2 := min{F[i,k] + F[i, j-k]} với k = 1,2, …, j div 2;

F[i,j] := min{t1, t2}

*Chương trình cài đặt:

program cut_hcn;

const fi='cut.inp';

fo='cut.out';

maxn=1001;

var f:text;

m,n,t:integer;

q:array[1..maxn,1..maxn] of integer;

procedure nhap;

var i,j:integer;

begin

assign(f,fi);

reset(f);

readln(f,m,n);

for i:=1 to m do

for j:=1 to n do

q[i,j]:=-1;

close(f);

end;

procedure xuli;

var min,l,k,i,j:integer ;

begin

75

for i:=1 to m do q[i,1]:=i;

for i:=1 to n do q[1,i]:=i;

for i:=2 to m do

for j:=2 to n do

if i=j then q[i,j]:=1

else

begin

min:=maxint;

for k:=1 to j div 2 do

if min>q[i,k]+q[i,j -k] then min:=q[i,k]+q[i,j-k] ;

for l:=1 to i div 2 do

if min>q[l,j]+q[i -l,j] then min:=q[l,j]+q[i-l,j] ;

q[i,j]:=min;

end;

{if i=-1 then

if (i mod j =0) or (j mod i =0) then

begin

if i>=j then q[i,j]:=i div j else q[i,j]:=j div i;

end

else

begin

min:=maxint;

for k:=1 to j div 2 do

if min>tinhq(i,k)+tinhq(i,j -k) then min:=tinhq(i,k)+tinhq(i,j -

k) ;

for l:=1 to i div 2 do

76

if min>tinhq(l,j)+tinhq(i-l,j) then

min:=tinhq(l,j)+tinhq(i -l,j) ;

q[i,j]:=min;

end;

tinhq:=q[i,j]; }

end;

procedure timkq(i,j:integer);

var k,l,tg:integer;

begin

if (i mod j =0) or (j mod i =0) then

begin

if i>=j then for tg:=1 to i div j do write(f,j,' ')

else for tg:=1 to j div i do write(f,i,' ');

end

else

begin

for k:=1 to (j div 2) do

if q[i,j]=(q[i,k]+q[i,j-k]) then

begin

timkq(i,k);

timkq(i,j-k);

exit;

end ;

for l:=1 to (i div 2) do

if q[i,j]=(q[l,j]+q[i-l,j]) then

begin

77

timkq(l,j);

timkq(i-l,j);

exit;

end;

end;

end;

procedure xuat;

var j,i:integer;

begin

assign(f,fo);

rewrite(f);

writeln(f,q[m,n]);

timkq(m,n);

close(f)

end;

BEGIN

nhap;

xuli;

xuat;

END.

Bài 18: Trò chơi với băng số: Rate This

Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như

sau: Có một băng hình chữ nhật được chia ra làm n ô vuông, đánh số từ trái

qua phải bắt đầu từ 1. Trên ô vuông thứ i người ta ghi một số nguyên dương a

i

,

i = 1, 2, …, n. Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn

một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải,

78

người chơi lựa chọn các ô i

1

, i

2

, …, i

k

. Khi đó điểm số mà người chơi đạt được

sẽ là:

a

i1

– a

i2

+ … + (-1)

k-1

a

ik

Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.

Dữ liệu vào: Đọc từ file văn bản Rate.inp có cấu trúc:

Dòng đầu tiên chứa số nguyên dương n ( n ≤ 10

6

) là số lượng ô của băng

số;

Dòng thứ hai chứa n số nguyên dương a

1

, a

2

, …, a

n

( a

i

≤ 10

4

, i = 1, 2, …, n )

ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất

một dấu cách.

Kết quả ra: Ghi ra file văn bản Rate.out có cấu trúc là:

Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt

chơi.

Ví dụ:

Rate.inp

Rate.out

7

4 9 2 4 1 3 7

17

Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 20.

*Chương trình cài đặt:

program rate_this;

const fi='ratethis.inp';

79

fo='ratethis.out';

maxn=1000000;

var f:text;

n,kq,dem:int64;

a,fl,fc,ds:array[1..maxn] of int64;

luuc,luul:array[1..maxn] of integer;

procedure nhap;

var i:longint;

begin

assign(f,fi);

reset(f);

readln(f,n);

for i:=1 to n do

read(f,a[i]) ;

close(f);

dem:=0;

fillchar(luul,sizeof(luul),0);

fillchar(luuc,sizeof(luuc),0);

end;

function max2so(cl,j,x,y:int64):int64;

begin

if x>y then max2so:=x

else begin

max2so:=y;

80

if cl=0 then luuc[j]:=1;

if cl=1 then luul[j]:=1;

end;

end;

procedure xuli;

var i,chanle:longint;

begin

fl[1]:=a[1];

fc[1]:=0;

for i:=2 to n do

begin

fl[i]:=max2so(1,i,fl[i-1],fc[i-1]+a[i]);

fc[i]:=max2so(0,i,fc[i-1],fl[i-1]-a[i]);

end;

if fl[n]>fc[n] then begin kq:=fl[n];chanle:=1;end

else begin kq:=fc[n];chanle:=0;end;

for i:=n downto 1 do

begin

if (chanle=1) and (luul[i]=1) then

begin

inc(dem);

ds[dem]:=i;

chanle:=0;

continue;

end;

81

if (chanle=0) and (luuc[i]=1) then

begin

inc(dem);

ds[dem]:=i;

chanle:=1;

end;

end;

end;

procedure xuat;

var i:longint;

begin

assign(f,fo);

rewrite(f);

writeln(f,kq);

for i:=dem downto 1 do

write(f,ds[i],' ');

close(f)

end;

BEGIN

nhap;

xuli;

xuat;

END.

82

Bài 19: Con kiến

Trên một sân hình chữ nhật MxN, được chia thành các ô vuông đơn v ị,

mỗiô chứa một lượng thức ăn. Một con kiến xuất phát từ ô (1,1) muốn đi qua

sân để đến dòng thứ M. Con kiến chỉ có thể đi theo một dòngchia nhỏ trên sân

ứng với một dòng của bảng chữ nhật hoặc đi theotrên một cột của sân. Hãy chỉ

ra đường đi giúp con kiến có được nhiều thức ăn nhất.

Dữ liệu vào: Đọc từ file văn bản FOOD.INP có cấu trúc:

Dòng đầu là 2 số M, N.

M dòng tiếp theo, mỗi dòng có N số tương ứng là lượng thức ăn có trong

M x N ô trên sân.

Kết quả ra: Ghi ra file văn bản FOOD.OUT có cấu trúc:

Dòng đầu là tổng lượng thức ăn nhiều nhất mà con kiến có thể ăn được.

Các dòng tiếp theo, mỗi dòng là 2 số tương ứng là toạ độ dòng, cột của ô

mà con kiến đi qua.

Ví dụ:

FOOD.INP

3 5

FOOD.OUT

45

1 1

2 1

2 2

2 3

83

3 3

*Hướng dẫn:

Trọng số ở đây là lượng thức ăn trên mỗi ô.

Quy tắc đi:

Dễ dàng tìm được công thức quy hoạch động là:

Gọi B[i,j] là lượng thức ăn lớn nhất đi từ ô (1,1) đến ô (i,j)

B[1,j]= A[1,j] với j = 1..N

B[i,1]= A[i,1]+B[i-1,1] với i = 2..M

B[i,j]=Max{B[i-1,j],B[i,j-1]} + A[i,j] với i = 2..M và j = 2..N

Bài 20: Sa mạc

Một bãi sa mạc có dạng hình chữ nhật MxN. Mỗi ô vuông đơn vị trên sa

mạc có một độ cao nào đó. Một người muốn đi từ bờ đầu này sang bờcuối

cùng bên kia. Người đó chỉ có thể đi từ ô đang đứng tới mộtô mới theo hướng

thẳng đứng chéo trái hoặc chéo phải. Giả thiết rằng người đó không được

vượt ra hai mép trái và phải của sa mạc.

Hãytìm đường đi sao cho người đó phải vượt qua quãng đường ngắn

nhất. Mỗi lần đi từ một ô sang ô mới tiếp theo người đó phải đi hết quãng

đường bằng độ chênh cao giữa hai ô đó.

84

SAMAC.INP

SAMAC.OUT

12(Quãng đường Min)

(1,3)(2,4) (3,3) (4,2) (5,2)

*Hướng dẫn:

Trọng số là độ chênh cao giữa hai ô liên tiếp.

Quy tắc đi.

Công thức tối ưu:

B[i,j] là quãng đường nhỏ nhất đi từ bờ đầu tiên đến ô (i,j).

B[1,j]= 0 với j = 1..N

B[i,1]= Min { B[i-1,1] + abs(A[i,1] - A[i-1,1]), B[i-1,2]+ abs(A[i,1] - A[i-1,2])}

Với i = 2..M

B[i,j]= Min { B[i-1,j -1] + abs(A[i,j] - A[i-1,j -1]),B[i-1,j] + abs(A[i,j] - A[i-1,j]),

B[i-1,j+1] + abs(A[i,j] - A[i-1,j+1])} Với i = 2..M, j = 2..N-1

B[i,N] = Min { B[i-1,N] + abs(A[i,N] - A[i-1,N]), B[i-1,N-1]+ abs(A[i,N] - A[i-

1,N-1])}, Với i = 2..M.

85

Bài 21: Quầy bán hàng.

Một siêu thị có M gian hàng, mỗi gian hàng gồm N ngăn chứa, mỗi ngăn

chứa được bố trí ở một phòng. Giám đốc siêu thị quyết định mở một đợt

khuyến mãi cho khách hàng với các quy tắc sau:

Mỗi gian hàng được bố trí trên từng tấng tương ứng từ tầng 1 đến M.

Mỗi tầng có N thang máy đi lên ứng với mỗi phòng.

Một khách hàng có thể mua sản phẩm tại một gian hàng nhưng chỉ có thể

đi theo một hướng (không được mua xong rồi quay trở lại nơi đã mua).

Khách hàng có thể đi thang máy lên tầng tiếp theo, nhưng phải mua ít nhất tại

một ngăn chứa ở tầng đó thì mới được phép đi lên tầng trên nữa.

Khách hàng mua hàng tại một ngăn chứa. Mỗi ngăn chứa quy định một số

lượng hàng mà người khách buộc phải mua khi đến ngăn chứa đó.

Nếu độ chênh số lượng hàng giữa hai ngăn chứa liên tiếp của một khách hàng

là một số may mắn đã biết trước. Khách hàng đó sẽ được khuyến mãi thêm

một số hàng bằng chính số may mắn đó.

Đến tầng thứ M, khách hàng chỉ có thể mua hàng tại duy nhất một ngăn

chứa.

Hãy giúp khách hàng lựa chọn điểm xuất phát và hướng đi sao cho mua

được nhiều hàng nhất (Kể cả số hàng được khuyến mãi).

Dữ liệu đầu vào cho trong FILE văn bản SHOP.INPcó cấu trúc như sau:

Dòng đầu là 3 số M,N, K (1<M, N, K ≤100), K là số các con số may mắn.

Dòng thứ hai ghi K con sốmay mắn.

M dòng tiếp theo ghi số lượng hàng quy định tại mỗi ngăn chứa. Mỗi

dòng gồm N số cách nhau bởi ít nhất một dấu trắng.

Kết quả ghi ra FILE văn bản SHOP.OUT như sau:

Dòng một là sốlượng hàng nhiều nhất.

86

Dòng hai điểm xuất phát và quá trình mua hàng. Mỗi ngăn chứa đi qua

được biểu diễn theo dạng ″(x,y) ″ trong đó (x,y) là vị trí của ngăn chứa.

Ví dụ:

SHOP.INP

SHOP.OUT

80 (Lượng hàng mua được Max)

(1,3) (1,2) (2,2) (2,1) (3,1) (3,2) (3,3) (3,4) (4,4)

*Hướng dẫn:

Trọng số ở đây là số lượng hàng tại các ngăn chứa. Đồng thời khi thoả

mãn điều kiện ″khuyến mãi ″ thì trọng số sẽ được tăng thêmsố lượng bằng số

các con số may mắn (phụ thuộc vào ô đứng trước).

Quy tắc đi:

:

Công thức quy hoạch động:

B[i,j] là lượng hàng max khi đi t ừ tầng 1 cho đến ngăn chứa (i,j)

B[0,j]= 0 với j =1..N

B[i,0]= 0 với i =1..M

87

B[i,j]= Max{B[i,j-1]+KM1, B[i-1,j] + KM2, B[i-1,k]+ SA[i,u]+KM3} + A[i,j]. Với

i

=1..M

,

j

=1..(N -1)

,

k

=(j+1)..M

,

u

=

j+1..k

KM1 là lượng hàng khuyến mãi nếu Abs(A[i,j]-A[i,j-1]) là con số may mắn.

KM2 là lượng hàng khuyến mãi nếu Abs(A[i,j]-A[i-1,j]) là con số may mắn.

KM3 là tổng số lượng hàng khuyến mãi nếu Abs(A[i,k]-A[i-1,k]) vàAbs(A[i,t]-

A[i,t+1])

với

t

=

j..(u-1)

là

các

con

số

may

mắn.

B[i,N]= Max{B[i,N-1]+KM1,B[i-1,N]+KM2}+A[i,N]

Với i =1..M

KM1 là lượng hàng khuyến mãi nếu abs(A[i,N]-A[i,N-1]) là con số may

mắn.

KM2 là lượng hàng khuyến mãi nếu abs(A[i,N]-A[i-1,N]) là con số may mắn.

Nhận xét:

Còn rất nhiều bài toán khác có dạng như một trong các bài toán cơ bản

này nhưng chung quy lại chúng ta đều có thể đưa nó về một dạng chung. Sau

đó dựa vào những nguyên tắc giải chung, ta đều có thể giải quyết dễ dàng.

Các dạng bài toán tổng quát này khi dữ liệu cho quá giới hạn khai báo bảng hai

chiều đều có thể giải quyết bằng cách quy hoạch liên tục trên 2mảng một

chiều. Sau mỗi bước quy hoạch phải thay đổi 2 mảng này saocho phù hợp với

bước quy hoạch tiếp theo. Cái khó của bài toán có dữ liệu lớn này là việc lưu

trữ trạng thái để sau khi quy hoạch toàn bộ ta còn có thể in ra file kết quả ″quá

trình đi ″ của phương án tối ưu.

88

Chương IV.

Một số đề tự giải

Bài 22: Chia thành nhiều nhóm có tổng bằng nhau

Cho n số a

1

, a

2

,..., a

n

(n ' NI*). Tìm cách chia số trên thành m nhóm sao cho

mỗi nhóm đều có tổng bằng nhau và m tìm được là lớn nhất.

Dữ liệu vào: Đọc vào từ file văn bản MNHOM.INP có cấu trúc như sau :

Dòng đầu ghi số n nguyên dương (N <= 10

4

)

Các dòng tiếp theo ghi n số a

1

, a

2

,..., a

n

, các số cách nhau ít nhất 1 dấu

cách;

Kết quả ra: Ghi ra file văn bản: MNHOM.OUT có cấu trúc như sau:

Dòng đầu tiên ghi số m lớn nhất tìm được

M dòng tiếp theo, mỗi dòng ghi các chỉ số của các phần tử thuộc cùng 1

nhóm;

Ví dụ:

MNHOM.INP

MNHOM.OUT

7

8 2 1 3 9 10 11

4

1 4

2 5

3 6

7

Bài 23: Bài toán xoay DOMINO

Cho N thanh DOMINO xếp theo chiều dọc như hình vẽ.

Ví dụ hình trên gồm 5 thanh DOMINO.

89

Mỗi thanh DOMINO gồm 2 phần, phần trên và phần dưới. Trên mỗi phần

có một số từ 1 đến 6. Yêu cầu đặt ra là hãy tìm cách xoay các thanh (xoay 180

độ) để sau khi xoay chênh lệch giữa tổng trên và tổng dưới là ít nhất. Giới hạn:

N<=1000.

Dữ liệu vào: Đọc từ file văn bản DOMINO.INP có cấu trúc như sau:

-

Dòng đầu tiên ghi số nguyên dương N

-

N dòng tiếp theo, mỗi dòng i ghi 2 số nguyên a

i

, b

i

(1 <=a

i

,b

i

<= 6)

tương ứng là số ở trên, ở dưới của thanh DOMINO thứ i;

Kết quả ra: Ghi ra file văn bản DOMINO.OUT có cấu trúc như sau:

-

Dòng đầu tiên ghi giá trị chênh lệch giữa tổng trên và tổng đưới;

-

Các dòng tiếp theo là chỉ số của các thanh DOMINO đ ược xoay;

Ví dụ:

DOMINO.INP

DOMINO.OUT

5

1 2

1 6

3 5

2 6

6 4

0

1

Bài 24: Bài toán ngân hàng trả tiền;

Một người đi lấy tiền ở một ngân hàng. Anh ta cần lấy một khoản đúng M

đồng. Ngân hàng có N đồng tiền A

1

, A

2

,.., A

N

. Hỏi ngân hàng có bao nhiêu cách

trả tiền.

Dữ liệu vào: Đọc từ file văn bản "MONEY.INP" có dạng:

Dòng đầu là hai số N và M (N <=100, M <= 10000)

Các dòng tiếp theo là các phần tử của mảng A.

90

Kết quả ra: Ghi ra file văn bản "MONEY.OUT" gồm một dòng duy nhất là

số cách trả tiền (Số cách trả tiền < Maxlongint)

Ví dụ:

Bài 25: Bài toán dãy có tổng chia hết cho k (đề thi toàn Quốc)

Cho một dãy số nguyên A

1

, A

2

,.., A

N

và một số k. Hãy tìm một dãy con

(không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia hết cho số k.

Dữ liệu vào: Đọc từ file văn bản "dayso.inp" có dạng:

Dòng 1 gồm 2 số N và k (N<=1000; k<=50)

Các dòng tiếp theo chứa các số của mảng A.

Kết quả ra: Ghi ra file văn bản "dayso.out" gồm một dòng ghi số phần tử

lớn nhất tìm được.

Ví dụ:

Bài 26: Xếp đồ vật vào ba lô (mỗi loại đồ vật có lýợng không hạn

chế);

Một chiếc ba lô có thể chứa được một khối lượng không quá W. Có N loại

đồ vật được đánh số từ 1 đến N, mỗi đồ vật loại i có khối A

i

và giá trị sử dụng C

i

(i=1, 2, …, N), số lượng đồ vật mỗi loại là không hạn chế. Hãy chọn các đồ vật

(mỗi loại bao nhiêu cái) để xếp vào ba lô sao cho tổng giá trị các đồ vật trong

ba lô là lớn nhất (nếu có thể xếp được).

Dữ liệu vào: Đọc từ file văn bản BALO.INP có cấu trúc như sau:

Dòng đầu ghi 2 số nguyên dương N, W (0 < N, W < 100).

Dòng i+1, 1 < i < N) ghi 2 số nguyên dương A

i

và C

i

(0<A

i

, C

i

<256)

91

Kết quả ra: Ghi ra file văn bản BALO.OUT có cấu trúc như sau:

Dòng đầu ghi tổng giá trị lớn nhất tìm được.

Từ dòng thứ 2, mỗi dòng ghi 2 số là: số hiệu loại đồ vật được chọn và số

lượng loại đồ vật đó.

Ví dụ:

BALO.INP

BALO.OUT

9 100

60 7

8 45

50 15

9 7

7 68

130 57

1 3

70 123

10 95

965

5 10

9 3

Bài 27: Đổi tiền

Ở đất nước Omega người ta chỉ tiêu tiền xu. Có N loại tiền xu, loại thứ i

có mệnh giá là a

i

đồng. Một người khách du lịch đến Omega du lịch với số tiền

M đồng. Ông ta muốn đổi số tiền đó ra tiền xu Omega để tiện tiêu dùng. Ông ta

cũng muốn số đồng tiền đổi được là ít nhất (cho túi tiền đỡ nặng khi đi đây đi

đó). Bạn hãy giúp ông ta tìm cách đổi tiền.

Dữ liệu: vào trong file văn bản Money.inp có dạng:

-

Dòng đầu là 2 số N và M (N <=100 và M <=10000)

-

Các dòng tiếp theo là N số tương ứng là các mệnh giá a

1

, a

2

, …,a

n

(với 0 < a

i

<= 1000)

92

Kết quả: Ghi ra file văn bản Money.out gồm một dòng duy nhất là số

đồng tiền ít nhất có thể đổi được (Số đồng xu < Maxlongint)

Ví dụ:

Money.inp

Money.out

4 10

1 2 3 4

3

Money.inp

Money.out

5 10

2 4 6 8 9

2

Bài 28:Chia tập

Xét tập chứa các số nguyên từ 1 tới N với N = 4K – 1 hoặc N = 4K. Tập các

số nguyên này có thể chia thành hai tập con có tổng các phần tử bằng nhau. Ví

dụ, với N = 7, ta có 4 cách chia thoả mãn điều kiện trên:

{2,3,4,5} và {1,6,7}

{1,3,4,6} và {2,5,7}

{1,2,5,6} và {3,4,7}

{1,2,4,7} và {3,5,6}

Với N cho trước, hãy tính số cách chia thành 2 tập con có tổng các phần

tử bằng nhau.

Dữ liệu: Vào từ file văn bản SET.INP, mỗi dòng chứa một số nguyên N (N

<= 100);

Kết quả: Đưa ra file văn bản SET.OUT số cách chia, mỗi dòng ứng với 1

dòng của file dữ liệu vào

Ví dụ:

SET.INP

SET.OUT

7

4

93

11

35

Bài 29: Đổi tiền xu

Nước Silverland sử dụng hệ thống tiền xu, trong đó các xu có m ệnh giá là

một số chính phương: 1,4,9,…,289(=17

2

). Với hệ thống này, để trả 10 xu ta có

4 cách:

Trả 10 đồng 1 xu,

Trả 1 đồng 4 xu và 6 đồng 1 xu,

Trả 2 đồng 4 xu và 2 đồng 1 xu,

Trả 1 đồng 9 xu và 1 đồng 1 xu.

Nhiệm vụ của bạn là xác định xem có bao nhiêu cách trả một số tiền cho

trước ở nước Silverland.

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

Gồm nhiều dòng, mỗi dòng một số nguyên dương không vượt quá 800.

Kết quả ra: Đưa ra file văn bản COIN.OUT là số cách trả ứng với từng

trường hợp.

Ví dụ:

COIN.INP

2

10

30

COIN.OUT
1
4

27

27

27

27

27

94

MỤC LỤC

I.1. Tư tưởng của phương pháp quy hoạch động.........................................................................3

I.1.1. Thuật toán chia để trị ......................................................................................................3
I.1.2. Hệ thức truy hồi ..............................................................................................................4
I.1.3. Lập trình động là gì?.......................................................................................................5
I.1.4. Phương pháp quy hoạch động ........................................................................................ 7

I.2. Các bước thực hiện giải bài toán bằng phương pháp quy hoạch động .................................8

I.2.1. Các bước cơ bản: ............................................................................................................8
I.2.2. Tổ chức cài đặt: ..............................................................................................................9
I.2.3 Khi nào dùng phương pháp quy ho ạch động? .................................................................9
Bài 1: Tìm dãy con không gi ảm nhiều phần tử nhất; ............................................................. 10

Hướng dẫn: ......................................................................................................................... 10
* Chương trình cài đặt:.......................................................................................................11

Bài 2: Dãy con chung dài nh ất;.............................................................................................. 13

Ví dụ: ..................................................................................................................................14
*Hướng dẫn: ....................................................................................................................... 14
*Chương trình cài đặt:........................................................................................................15

Bài 3: Dãy con có tổng bằng S .............................................................................................. 17
Bài 4: Xếp đồ vật vào ba lô (mỗi đồ vật chỉ có 1) .................................................................20

*Hướng dẫn ........................................................................................................................ 21
*Chương trình cài đặt:........................................................................................................22

Chương III: Bài tập chọn lọc .....................................................................................................26

Bài 5: Bố trí phòng họp; ........................................................................................................26

* Hướng dẫn: ...................................................................................................................... 27
* Chương trình cài đặt:.......................................................................................................27

Bài 6: Cho thuê máy tính; ......................................................................................................30

*Hướng dẫn: ....................................................................................................................... 31
* Chương trình cài đặt:.......................................................................................................31

Bài 7: Nối điểm ...................................................................................................................... 34

*Hướng dẫn: ....................................................................................................................... 35
* Chương trình cài đặt:.......................................................................................................35

Bài 8: Dãy con đổi chiều, đối dấu dài nhất; ...........................................................................38

* Hướng dẫn: ...................................................................................................................... 39
* Chương trình cài đặt:.......................................................................................................39

Bài 9: Số phép biến đổi ít nhất ............................................................................................... 43

* Hướng dẫn: ...................................................................................................................... 43
*Chương trình cài đặt:........................................................................................................44

Bài 10: Xâu đối xứng; ...........................................................................................................47

*Hướng dẫn: ....................................................................................................................... 47
*Chương trình cài đặt:........................................................................................................47

Bài 11: Bài toán chia k ẹo .......................................................................................................50

95

*Hướng dẫn: ....................................................................................................................... 50
* Chương trình cài đặt:.......................................................................................................50

Bài 12: Mua cá theo lýợng (Olympic Balkan 2000) ; ............................................................ 54

* Hướng dẫn: ...................................................................................................................... 55
* Chương trình cài đặt:.......................................................................................................55

Bài 13: Điền dấu hỏi vào biểu thức ....................................................................................... 57

*Hướng dẫn: ....................................................................................................................... 57
* Chương trình cài đặt:.......................................................................................................58

Bài 14: Chia thành hai nhóm có tích l ớn nhất (ACM 10690) ................................................61

*Hướng dẫn: ....................................................................................................................... 62
*Chương trình cài đặt:........................................................................................................62

Bài 15: Bài toán mua bán hàng .............................................................................................. 64

* Chương trình cài đặt:.......................................................................................................65

Bài 16: Lịch thuê nhân công ..................................................................................................70

* Hướng dẫn:...................................................................................................................... 71

Bài 17: Cắt hình chữ nhật ......................................................................................................72

*Hướng dẫn:....................................................................................................................... 73
*Chương trình cài đặt:........................................................................................................74

Bài 18: Trò chơi với băng số: Rate This ................................................................................77

*Chương trình cài đặt:........................................................................................................78

Bài 19: Con kiến .................................................................................................................... 82

*Hướng dẫn: ....................................................................................................................... 83

Bài 20: Sa mạc ....................................................................................................................... 83

*Hướng dẫn: ....................................................................................................................... 84

Bài 21: Quầy bán hàng...........................................................................................................85

*Hướng dẫn:....................................................................................................................... 86

Nhận xét: ................................................................................................................................ 87
Bài 22: Chia thành nhiều nhóm có tổng bằng nhau ............................................................... 88
Bài 23: Bài toán xoay DOMINO ........................................................................................... 88
Bài 24: Bài toán ngân hàng tr ả tiền; ...................................................................................... 89
Bài 25: Bài toán dãy có t ổng chia hết cho k (đề thi to àn Quốc) ............................................90
Bài 26: Xếp đồ vật vào ba lô (mỗi loại đồ vật có lýợng không hạn chế); ............................. 90
Bài 27: Đổi tiền ...................................................................................................................... 91
Bài 28:Chia tập ...................................................................................................................... 92
Bài 29: Đổi tiền xu ................................................................................................................. 93

96

Tài liệu tham khảo

1. Trần Đỗ Hùng, Chuyên đề bồi dưỡng HSG Tin học THPT,NXB GD 2007

2. Nguyễn Quý Khang, Bài tập Pascal, NXB QGHN 2002

3. Nguyễn Xuân My, Một số vấn đề chọn lọc trong môn Tin học, NXB GD

2002

4. Nguyễn Xuân My, Bài tập lập trình Pascal, NXB TK 1997

5. Báo TH&NT 1999 - 2006

6. Trang web:

http://www.wikipedia.org

7. Trang web:

http://www.vnoi.info

8. Trang web:

http://www.ddth.com