Mẹo Cho N và dãy số nguyên a1 aN hãy tính trung bình cộng các số hạng trong dãy có giá trị là chẵn Chi tiết

Hướng dẫn:

Gọi $L_i$ là số thành phần của dãy con đổi dấu có thành phần ở đầu cuối là $A_i$ và thành phần ở đầu cuối to nhiều hơn thành phần đứng trước. Tương tự, $P_i$ là số thành phần của dãy con đổi dấu có thành phần ở đầu cuối là $A_i$ và thành phần ở đầu cuối nhỏ hơn thành phần đứng trước.

Ta thuận tiện và đơn thuần và giản dị suy ra:

$L_i = max(1, P_j + 1)$, với mọi $j$ thỏa mãn nhu cầu: $j le i-L$ và $A_i – U le A_j < A_i$.
$P_i = max(1, L_j + 1)$, với mọi $j$ thỏa mãn nhu cầu: $j le i-L$ và $A_i < A_j le A_i + U$.

Dãy số WAVIO

Bài toán:

Dãy số Wavio là dãy số nguyên thỏa mãn nhu cầu những tính chất: những thành phần đầu sắp xếp thành 1 dãy tăng dần đến 1 thành phần đỉnh tiếp theo đó giảm dần. Ví dụ dãy số 1 2 3 4 5 2 1 là một trong dãy Wavio độ dài 7. Cho 1 dãy gồm $N$ số nguyên, hãy chỉ ra một dãy con Wavio có đọ dài lớn số 1 trích ra từ dãy đó.

Hướng dẫn:

$L1_i$ là mảng ghi độ dài lớn số 1 của một dãy con tăng dần trích ra từ dãy $N$ thành phần Tính từ lúc thành phần 1 đến thành phần $a_i$.

$L2_i$: mảng ghi độ dài lớn số 1 của dãy con giảm dần trích ra từ dãy $N$ thành phần Tính từ lúc thành phần $A_N$ đến $A_i$. Ta tìm thành phần $j$ trong 2 mảng $L1$, $L2$ thỏa mãn nhu cầu $L1_j + L2_j$ lớn số 1.

Xếp những khối đá

Bài toán:

Cho $N$ khối đá $(N le 5000)$.

Các khối đá đều phải có dạng hình hộp chữ nhật và được đặc trưng bới 3 kích thước: dài, rộng, cao. Một cách xây dựng tháp là một cách đặt một số trong những những khối đá trong những khối đá đã cho chồng lên nhau theo quy tắc:

Chiều cao mỗi khối đá là kích thước nhỏ nhất trong 3 kích thước.
Các mép của khối đá được đặt tuy nhiên tuy nhiên với nhau sao cho không còn phần nào của khối trên nằm chìa ra ngoài khối dưới.

Hãy chỉ ra phương pháp để xây dựng được một chiếc tháp sao cho số khối đá được sử dụng là nhiều nhất.

2. Vali (B)

Có $n$ dụng cụ, vật thứ $i$ có trọng lượng $A_i$ và giá trị $B_i$. Hãy lựa chọn ra một số trong những những dụng cụ, mỗi vật một chiếc để xếp vào 1 vali có trọng lượng tối đa $W$ sao cho tổng mức của vali là lớn số 1.

2.2. Công thức

Hàm tiềm năng: $f$: tổng mức của vali.

Nhận xét: giá trị của vali tùy từng 2 yếu tố: có bao nhiêu vật đang rất được xét và trọng lượng của những vật. Do đó bảng phương án sẽ là bảng 2 chiều:
– $L(i,j)$: tổng mức lớn số 1 của vali khi xét từ vật 1 .. vật $i$ và trọng lượng của vali chưa vượt quá $j$. Chú ý rằng khi xét đến $L[i,j]$ thì những giá trị trên bảng phương án đều đã được tối ưu.

Tính $L(i,j)$: vật đang xét là $a_i$ với trọng lượng của vali không được quá $j$. Có 2 kĩ năng xẩy ra:

Nếu chọn $A_i$ đưa vào vali, trọng lượng vali trước đó phải không thật $j – A_i$. Vì mỗi vật chỉ được chọn một lần nên giá trị lớn số 1 của vali lúc đó là $L(i-1, j – A_i) + B_i$.
Nếu không chọn $A_i$, trọng lượng của vali là như cũ (như trước lúc chọn $A_i$): $L(i-1,j)$.

Tóm lại ta có $L[i,j] = max(L(i-1, j – A_i) + B_i, L(i-1, j))$.

2.3. Cài đặt

For i:=1 to n do For j:=1 to W do If b[i]<=j then L[i,j]:=max(L[ i-1,j-A[i] ] + B[i], L[i-1,j]) else L[i,j]:=L[i-1,j];

2.4. Một số bài toán khác

Dãy con có tổng bằng S

Bài toán:

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$.

Hướng dẫn:

Đặt $L[i,t]=1$ nếu hoàn toàn có thể tạo ra tổng $t$ từ một dãy con của dãy gồm những thành phần $A_1,A_2,…,A_i$. trái 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 hoàn toàn 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$.

Cài đặt:

Nếu vận dụng luôn công thức trên thì ta cần dùng bảng phương án hai chiều. Ta hoàn toàn có thể nhận xét rằng để tính dòng thứ $i$, ta chỉ việc dòng $i-1$. Bảng phương án khi đó chỉ việc 1 mảng 1 chiều $L[0..S]$ và được xem như sau:

L[t]:=0; L[0]:=1; for i := 1 to n do for t := S downto a[i] do if (L[t]=0) and (L[t-a[i]]=1) then L[t]:=1;

Dễ thấy độ phức tạp bộ nhớ của cách setup trên là $O(m)$, độ phức tạp thời hạn là $O(n * m)$, với $m$ là tổng của $n$ số. Hãy tự kiểm tra xem tại sao vòng for thứ hai lại là for downto chứ không phải là for to.

Chia kẹo

Bài toán:

Cho $n$ gói kẹo, gói thứ $i$ có $a_i$ viên. Hãy chia những gói thành 2 phần sao cho chênh lệch giữa 2 phần là tối thiểu.

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 số 1 thoả mãn:

$S le T/2$.
Có một dãy con của dãy $a$ có tổng bằng $S$.

Khi này sẽ có đượ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 những thành phần là những gói kẹo thuộc phần thứ nhất. Phần thứ hai là những gói kẹo còn sót lại.

Market (Olympic Balkan 2000)

Bài toán:

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 đó. 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 6kg sẽ phải lấy con cá thứ hai 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 thứ nhất mua cá, có bao nhiêu lượng bạn hoàn toàn có thể chọn?

Hướng dẫn

Thực chất bài toán là tìm những số $S$ mà có một dãy con của dãy $a$ có tổng bằng $S$. Ta hoàn toàn có thể dùng phương pháp ghi lại của bài chia kẹo ở trên rồi đếm những giá trị $t$ mà $L[t]=1$.

Điền dấu

Bài toán:

Cho $n$ số tự nhiên $A_1,A_2, …,A_N$. Ban đầu những số được đặt liên tục theo như đúng thứ tự cách nhau bởi dấu “?”: A1 ? A2 ? … ? AN. Cho trước số nguyên $S$, có cách nào thay những 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?

Hướng dẫn:

Đặt $L[i,t]=1$ nếu hoàn toàn có thể điền dấu vào $i$ số thứ nhất 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 vấn đáp của bài toán là có.

Khi setup, hoàn toàn 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 (để lưu dòng $i$ và dòng $i-1$). Chú ý là chỉ số theo $t$ của những 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 toàn bộ chúng ta dùng cả dấu – nên hoàn toàn có thể tạo ra những tổng âm.

Bài này còn có một biến thể là đặt dấu sao cho kết quả là một số trong những chia hết cho $k$. Ta có thuật giải tương tự bài toán trên bằng phương pháp thay những phép cộng, trừ bằng những phép cộng và trừ theo modulo $k$ và dùng mảng ghi lại với những giá trị từ 0 đến $k-1$ (là những số dư hoàn toàn có thể có khi chia cho $k$). Đáp số của bài toán là $L[n,0]$.

Expression

Bài toán:

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 số 1.

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 sót 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 ghi lại ta xác lập đượ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.

Farmer (IOI 2004)

Bài toán

Một người dân có $N$ mảnh đất nền trống và $M$ dải đất. Các mảnh đất nền trống hoàn toàn có thể xem là một tứ giác và những dải đất thì coi như một đường thẳng. Dọc theo những dải đất ông ta trồng những cây bách, dải đất thứ $i$ có $A_i$ cây bách. Ông ta cũng trồng những cây bách trên viền của những mảnh đất nền trống, mảnh đất nền trống thứ $j$ có $B_j$ cây bách. Cả ở trên những mảnh đất nền trống và dải đất, xen giữa 2 cây bách ông ta trồng một cây ôliu. Ông ta cho con trai được chọn những mảnh đất nền trống và dải đất tuỳ ý với Đk tổng số cây bách không vượt quá $Q.$. Người con trai phải chọn thế nào để sở hữu nhiều cây ôliu (loài cây mà anh ta thích) nhất.

Hướng dẫn

Dễ thấy mảnh đất nền trống thứ $i$ có $A_i$ cây ôliu và dải đất thứ $j$ có $B_j-1$ cây ôliu. Coi những mảnh đất nền trống và dải đất là những “dụng cụ”, dụng cụ thứ $k$ có khối lượng $W_k$ và giá trị $V_k$ (nếu $k$ là mảnh đất nền trống $i$ thì $W_k=V_k=A_i$, nếu $k$ là dải đất $j$ thì $W_k=B_j$, $V_k=B_j-1$). Ta cần chọn những “dụng cụ”, sao cho tổng “khối lượng” của chúng không vượt $Q.$ và tổng “giá trị” là lớn số 1. Đây đó đó là bài toán xếp balô đã trình diễn ở trên.

3. Biến đổi xâu

Cho 2 xâu $X$, $F$. Xâu gốc có $n$ kí tự $X_1 X_2 … X_n$, xâu đích có $m$ kí tự $F_1 F_2 … F_m$. Có 3 phép biến hóa:

Chèn 1 kí tự vào sau kí tự thứ $i$: I i C

Thay thế kí tự ở vị trí thứ $i$ bằng kí tự $C$: R i C

Xoá kí tự ở vị trí thứ $i$: D i

Hãy tìm số tối thiểu những phép biến hóa để biến xâu $X$ thành xâu $F$.

3.2. Hướng dẫn

Hàm tiềm năng: $f$: số phép biến hóa.

Dễ thấy số phép biến hóa tùy từng vị trí $i$ đang xét của xâu $X$ và vị trí $j$ đang xét của xâu $F$. Do vậy để setup cho bảng phương án ta sẽ dùng mảng 2 chiều.

Gọi $L[i,j]$ là số phép biến hóa tối thiểu để 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 $F_j$ gồm $j$ kí tự phần đầu của $F$ ($F_j = F[1..j]$).

Dễ thấy $L[0,j]=j$ và $L[i,0]=i$.

Có 2 trường hợp xẩy ra:

Nếu $X[i] = F[j]$:
$X_1 X_2 … X_i-1$ $X_i$
$F_1 F_2 … F_j-1$ $X_i$
thì ta chỉ phải biến hóa xâu $X_i-1$ thành xâu $F_j-1$. Do đó $L[i,j]=L[i-1,j-1]$.

trái lại, ta có 3 cách biến hóa:

Xoá kí tự $X_i$:
$X_1 X_2 … X_i-1$
$F_1 F_2 … F_j-1$ $F_j$
Xâu $X_i-1$ thành $F_j$. Khi đó $L[i,j]=L[i-1,j]+1$. (Cộng 1 là vì ta đã dùng 1 phép xóa)

Thay thế $X_i$ bởi $F_j$:

$X_1 X_2 … X_i-1$ $F_j$
$F_1 F_2 … F_j-1$ $F_j$
Xâu $X_i-1$ thành $F_j-1$. Khi đó $L[i,j]=L[i-1,j-1]+1$.

Chèn $F_j$ vào sau $X_i$:

$X_1 X_2 … X_i$ $F_j$
$F_1 F_2 … F_j-1$ $F_j$
Xâu $X_i$ thành $F_j-1$. Khi đó $L[i,j]=L[i,j-1]+1$

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

L[0,j]=j
L[i,0]=i

L[i,j] =L[i−1,j−1] nếu $X_i = Y_j$.

L[i,j] = min(L[i−1,j], L[i,j−1], L[i−1,j−1]) + 1 nếu $X_i ne F_j$.

Bài này ta hoàn toàn có thể tiết kiệm chi phí biến hơn bằng phương pháp dùng 2 mảng 1 chiều tính lẫn nhau và một mảng ghi lại 2 chiều để truy vết.

3.3. Một số bài toán khác

Xâu con chung dài nhất

Bài toán:

Cho 2 xâu $X$, $Y$. Hãy tìm xâu con của $X$ và của $Y$ có độ dài lớn số 1. Biết xâu con của một xâu thu được khi xóa một số trong những kí tự thuộc xâu đó (hoặc không xóa kí tự nào).

Công thức QHĐ:

Gọi $L[i,j]$ là độ dài xâu con chung dài nhất của xâu $X_i$ gồm $i$ kí tự phần đầu của $X$ ($X_i = X[1..i]$) và xâu $Y_j$ gồm $j$ kí tự phần đầu của $Y$ ($Y_j = Y[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 $X_i = Y_j$

L[i,j] = max(L[i−1,j], L[i,j−1]) nếu $X_i ne Y_j$.

Cài đặt:

Bảng phương án là một mảng 2 chiều L[0..m,0..n] để lưu những giá trị của hàm QHĐ $L[i,j]$.

Đoạn chương trình setup công thức QHĐ trên như sau:

for i:=0 to m do L[i,0]:=0;
for j:=0 to n do L[0,j]:=0; for i:=1 to m do for j:=1 to n do if X[i]=Y[j] then L[i,j]:=L[i-1,j-1]+1 else L[i,j]:=max(L[i-1,j],L[i,j-1]]);

Như vậy độ phức tạp bộ nhớ của bài toán là $O(n^2)$, độ phức tạp thời hạn là $O(n^2)$.

Có một phương pháp setup tốt hơn, chỉ với độ phức tạp bộ nhớ $O(n)$ nhờ vào nhận xét sau: để tính ô $L[i,j]$ của bảng phương án, ta chỉ việc 3 ô $L[i-1,j-1]$, $L[i-1,j]$ và $L[i,j-1]$. Tức là để tính dòng $L[i]$ thì chỉ việc dòng $L[i-1]$. Do đó ta chỉ việc 2 mảng 1 chiều để lưu dòng vừa tính (P) và dòng đang tính (L) mà thôi. Cách setup mới như sau:

for j:=0 to n do P[j]:=0; for i:=1 to m do begin L[0] := 0; for j:=1 to n do if X[i]=Y[j] then L[i,j]:=P[j-1]+1 else L[i,j]:=max(P[j], L[j-1]); P := L; end;

Bắc cầu

Bài toán:

Hai nước Alpha và Beta nằm ở vị trí hai bờ sông Omega, Alpha nằm ở vị trí bờ bắc và có $M$ thành phố được đánh số từ là 1 đến $M$, Beta nằm ở vị trí bờ nam và có $N$ thành phố được đánh số từ là 1 đến $N$ (theo vị trí từ đông sang tây). Mỗi thành phố của nước này thường có quan hệ kết nghĩa với một số trong những thành phố của nước kia. Để tăng cường tình hữu nghị, hai nước muốn xây những cây cầu bắc qua sông, mỗi cây cầu sẽ là nhịp cầu nối 2 thành phố kết nghĩa. Với yêu cầu là những cây cầu không được cắt nhau và mỗi thành phố chỉ là đầu phía trên cầu cho nhiều nhất là một cây cầu, hãy chỉ ra cách bắc cầu được nhiều cầu nhất.

Hướng dẫn:

Gọi những thành phố của Alpha lần lượt là $A_1,A_2,…, A_M$; những thành phố của Beta là $B_1,B_2,…,B_N$. Nếu thành phố $A_i$ và $B_j$ kết nghĩa với nhau thì coi $A_i$ “bằng” $B_j$. Để những cây cầu không cắt nhau, nếu ta đã chọn cặp thành phố $(A_i,B_j)$ để xây cầu thì cặp tiếp theo phải là cặp $(A_u,B_v)$ sao cho $u>i$ và $v>j$. Như vậy những cặp thành phố được chọn xây cầu hoàn toàn có thể xem là một dãy con chung của hai dãy $A$ và $B$.

Bài toán của toàn bộ chúng ta trở thành bài toán tìm dãy con chung dài nhất, ở đây hai thành phần “bằng” nhau nếu chúng có quan hệ kết nghĩa.

Palindrome (IOI 2000)

Bài toán:

Một xâu gọi là xâu đối xứng (palindrome) 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ối thiểu cần thêm vào $S$ để $S$ trở thành xâu đối xứng.

Hướng dẫn:

Bài toán này còn có một công thức QHĐ như sau:

Gọi $L[i,j]$ là số kí tự tối thiểu 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 ne S_j$

Bạn đọc thuận tiện và đơn thuần và giản dị hoàn toàn có thể kiểm chứng công thức đó. Ta hoàn toàn có thể setup trực tiếp công thức đó bằng phương pháp đệ quy có nhớ. Tuy nhiên khi đó độ phức tạp bộ nhớ là $O(n^2)$. Có một phương pháp setup tiết kiệm chi phí hơn, hoàn toàn có thể tìm hiểu thêm ở nội dung bài viết của Nguyễn Hoành Tiến

Ta có thuật toán đơn thuần và giản dị hơn như sau:

Gọi $P$ là xâu hòn đảo của $S$ và $T$ là xâu con chung dài nhất của $S$ và $P$. Khi đó những kí tự của $S$ không thuộc $T$ cũng là những 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=edbabcd, xâu hòn đảo của $S$ là P=dcbabde. Xâu con chung dài nhất của $S$ và $P$ là T=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.

4. Vali (A)

Cho $n$ vật, vật $i$ nặng $A_i$ và có mức giá trị $B_i$. Hãy lựa chọn ra một số trong những vật khiến cho vào balô sao cho tổng khối lượng không vượt quá $W$ và tổng mức là lớn số 1. Chú ý rằng mỗi vật hoàn toàn có thể được chọn nhiều lần.

4.2. Công thức

Gọi $L(i,j)$ là tổng mức lớn số 1 khi được chọn $i$ vật từ là 1 đến $i$ cho vào balô với tổng khối lượng không vượt quá $j$. $L(n,W)$ sẽ là đáp số của bài toán (là giá trị lớn số 1 đã có được nếu lọc $n$ vật và tổng khối lượng không vượt quá $W$).

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,t-A_i) + B_i)$ nếu $t ge A_i$

Trong số đó: $L(i-1,t)$ là giá trị đã có được nếu không đưa vật $i$ vào balô, $L(i,t-A_i) + B_i$ là giá trị đã có được nếu lọc vật $i$.

4.3. Cài đặt

Ta hoàn toàn có thể dùng một mảng 2 chiều để lưu bảng phương án, tuy nhiên nhờ vào nhận xét rằng để tính dòng $i$ của bảng phương án chỉ việc dòng $i-1$, ta chỉ việc 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.

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<a[i] then L[t]:=P[t] else L[t] := max(P[t],L[t-a[i]]+b[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, tiếp theo này lại sở hữu gán L[t]:=P[t] với những giá trị t<a[i] là không thiết yếu. Bạn đọc hoàn toàn có thể tự tăng cấp cải tiến để chương trình tối ưu hơn.
Độ phức tạp bộ nhớ là $O(m)$ và độ phức tạp thời hạn là $O(m * n)$.

4.4. Một số bài toán khác

Đổi tiền

Bài toán

Ở giang sơn 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 xu tiền đổi được là tối thiểu (cho ví tiền đỡ nặng khi đi đây đi đó). Bạn hãy giúp ông ta tìm cách đổi tiền.

Hướng dẫn

Bài toán này khá giống bài toán xếp balô (“khối lượng” là mệnh giá, “giá trị” là một trong), chỉ có một thay đổi nhỏ: tổng mức yêu cầu là nhỏ nhất.

Do đó ta cũng xây dựng hàm QHĐ một cách tương tự: Gọi $L[i,t]$ là số đồng xu tối thiểu nếu đổi $t$ đồng ra $i$ loại tiền xu (từ là 1 đến $i$). Công thức tính $L[i,t]$ như sau:

$L[i,0]=0$
$L[0,t]= inf$ với $t>0$.
$L[i,t]=L[i-1,t]$ nếu $t<A[i]$.
$L[i,t]=min(L[i-1,t], L[i,t-A[i]]+1)$ nếu $t ge A_i$.

Công thức này khác công thức của bài xếp balô ở đoạn: dùng hàm min chứ không phải hàm max (vì cần tìm cách chọn thấp hơn).

5. Nhân ma trận

Nhân một ma trận kích thước $m * n$ với một ma trận $n * p.$, số phép nhân phải thực thi là $m * n * p.$. Mặt khác phép nhân những ma trận có tính phối hợp, tức là: $(A * B) * C = A * (B * C)$

Do đó khi tính tích nhiều ma trận, ta hoàn toàn có thể thực thi theo những trình tự rất khác nhau, mỗi trình tự tính sẽ quyết định hành động số phép nhân cần thực thi.

Cho $N$ ma trận $A_1, A_2, …, A_N$, ma trận $A$ có kích thước là $d_i-1 * d_i$. Hãy xác lập trình tự nhân ma trận $A_1 * A_2 * … * A_N$ sao cho số phép nhân cần thực thi là tối thiểu.

5.2. Công thức

Gọi $F(i,j)$ là số phép nhân để tính tích những ma trận từ $A_i$ đến $A_j$ $(A_i * A_i+1 * … * A_j)$.

$F[i,i]=0$.
$F[i,i+1]=d_i-1 * d_i * d_i+1$
$F[i,j] = min(F[i,k]+F[k+1,j] + d_i-1 * d_k * d_j$ với $k=i+1,i+2,…,j-1$

Công thức hơi phức tạp nên tôi xin lý giải như sau:

$F[i,i]=0$ là hiển nhiên.
$F[i,i+1]$ là số phép nhân khi nhân $A_i$ và $A_i+1$. $A_i$ có kích thước $d_i-1 * d_i$, $A_i+1$ có kích thước $d_i * d_i+1$, do đó $F[i,i+1]=d_i-1 * d_i * d_i+1$
Với $j>i+1$ thì ta thấy hoàn toàn có thể tính $A_i * A_i+1 * … * A_j$ bằng phương pháp chọn một vị trí $k$ nào đó để tại vị ngoặc theo trình tự: $A_i * A_i+1 * … * A_j = (A_i..A_k) * (A_k+1..A_j)$

Ma trận kết quả của phép nhân $(A_i..A_k)$ có kích thước $d_i-1 * d_k$, ma trận kết quả của phép nhân $(A_k+1..A_j)$ có kích thước $d_k * d_j$. Với cách đặt đó ta sẽ mất $F[i,k]$ phép nhân để sở hữu kết quả trong dấu ngoặc thứ nhất, mất thêm $F[k+1,j]$ phép nhân để sở hữu kết quả trong dấu ngoặc thứ hai, và ở đầu cuối mất $d_i-1 * d_k * d_j$ để nhân 2 ma trận kết quả đó. Từ đó tổng số phép nhân của cách đặt đó là: $F[i,k] + F[k+1,j] + d_i-1 * d_k * d_j$.

Ta chọn vị trí $k$ cho số phép nhân tối thiểu.

5.3. Cài đặt

Bảng phương án là một mảng 2 chiều $F$ để lưu $F[i,j]$. Chú ý khi setup là để tính được $F[i,j]$, ta phải tính $F[i,k]$ và $F[k+1,j]$ trước. Phương pháp đơn thuần và giản dị để làm điều này là phương pháp đệ quy có nhớ.

Tuy nhiên nhờ vào nhận xét là trong công thức QHĐ: $j-i$ to nhiều hơn $k-i$ và $j-k$, ta hoàn toàn có thể tính theo trình tự khác: tính những thành phần $F[i,j]$ với $j-i$ từ nhỏ đến lớn (không phải là tính những giá trị $F[i,j]$ với $i$, $j$ từ nhỏ đến lớn như vẫn thực hiện). Với cách đó, khi tính đến $F[i,j]$ thì ta đã có $F[i,k]$ và $F[k+1,j]$.

Đoạn chương trình tính bảng phương án như sau:

for i:=1 to n do F[i,i]:=0; for i:=1 to n-1 do F[i,i+1] := d[i-1]*d[i]*d[i+1]; for m:=2 to n-1 do begin for i:=1 to n-m do begin j:=i+m; F[i,j]:=oo; for k:=i+1 to j-1 do F[i,j]:=min(F[i,j], F[i,k]+F[k+1,j]+d[i-1]*d[k]*d[j]); end;
end;

Với cách setup trên, độ phức tạp bộ nhớ là $O(n^2)$, độ phức tạp thời hạn là $O(n^3)$.

5.4. Một số bài toán khác

Chia đa giác

Bài toán

Cho một đa giác lồi $N$ đỉnh. Bằng những đường chéo không cắt nhau, ta hoàn toàn có thể chia đa giác thành $N-2$ tam giác. Hãy xác lập cách chia có tổng những đường chéo ngắn nhất.

Hướng dẫn

Để đơn thuần và giản dị ta coi mọi đoạn thẳng nối 2 đỉnh đều là “đường chéo” (nếu nối 2 đỉnh trùng nhau hoặc 2 đỉnh liên tục thì có độ dài bằng 0).

Gọi $F(i,j)$ là tổng độ dài những đường chéo khi chia đa giác gồm những đỉnh từ $i$ đến $j$ thành những tam giác. Nếu $j<i+3$ thì đa giác đó có thấp hơn 4 đỉnh, tránh việc phải chia nên $F(i,j)=0$. trái lại ta xét cách chia đa giác đó bằng phương pháp chọn một đỉnh $k$ nằm trong tâm $i$, $j$ và nối $i$, $j$ với $k$. Khi đó $F[i,j]=F[i,k]+F[k,j]+d[i,k]+d[k,j]$ với $d(i,k)$ là độ dài đường chéo $(i,k)$.

Tóm lại công thức QHĐ như sau:

$F[i,j]=0$ với $j<i+3$.
$F[i,j]=min(F[i,k]+F[k,j]+d[i,k]+d[k,j])$ với $k=i+1,…j-1$. $F[1,n]$ là tổng đường chéo của cách chia tối ưu.

Biểu thức số học (IOI 1999)

Bài toán

Cho biểu thức $A_1 cdot A_2 cdot … cdot A_N$, trong số đó $A_i$ là những số thực không âm và $cdot$ là một phép toán + hoặc * cho trước. Hãy đặt những dấu ngoặc để biểu thức thu được có kết quả lớn số 1.

Hướng dẫn

Gọi $F[i,j]$ là giá trị lớn số 1 hoàn toàn có thể có của biểu thức $A_i cdot A_i+1 cdot … cdot A_j$. Dễ thấy nếu $i=j$ thì $F[i,j]=A_i$, nếu $j=i+1$ thì $F[i,j]=A_i cdot A_j$. Nếu $j>i+1$ thì hoàn toàn có thể tính biểu thức $A_i cdot A_i+1 cdot … cdot A_j$ bằng phương pháp phân thành 2 nhóm: $(A_i cdot A_i+1 cdot … cdot A_k) cdot (A_k+1 cdot … cdot A_j)$, Khi đó $F[i,j]=F[i,k] cdot F[k+1,j]$.

Tóm lại, công thức QHĐ là:

$F[i,i]=A_i$
$F[i,i+1]=A_i cdot A_i+1$
$F[i,j]=max(F[i,k] cdot F[k+1,j])$ với $k=i+1,i+2,..j-1$.

(Chú là là những hạng tử của dãy đều không âm và những phép toán là + hoặc * nên $F[i,k]$ và $F[k+1,j]$ đạt max thì $F[i,k] cdot F[k+1,j]$ cũng đạt max).

6. Ghép cặp

Có $n$ lọ hoa sắp thẳng hàng và $k$ bó hoa được đánh số thứ tự từ nhỏ đến lớn. Cần cắm $k$ bó hoa trên vào $n$ lọ sao cho hoa có số thứ tự nhỏ phải đứng trước hoa có số thứ tự lớn. Giá trị thẩm mỹ và làm đẹp tương ứng khi cắm hoa $i$ vào lọ thứ $j$ là $v(i,j)$. Hãy tìm 1 cách cắm sao cho tổng mức thẫm mỹ là lớn số 1. Chú ý rằng mỗi bó hoa chỉ được cắm vào 1 lọ và mỗi lọ cũng chỉ cắm được một bó hoa.

6.2. Công thức

Nhận xét rằng bài toán nêu trên là một bài toán ghép cặp có yêu cầu về thứ tự nên ta hoàn toàn có thể xử lý và xử lý bằng phương pháp QHĐ.

Hàm tiềm năng: $f$: tổng mức thẩm mỹ và làm đẹp của cách cắm.

Giá trị thẩm mỹ và làm đẹp tùy từng những hoa và những lọ đang rất được xét nên ta sẽ dùng mảng 2 chiều để lưu bảng phương án.

$L(i,j)$: tổng mức thẩm mỹ và làm đẹp lớn số 1 khi xét đến hoa $i$ và lọ $j$. Khi tính $L(i,j)$ hoa đang xét sẽ là hoa $i$ và lọ $j$.

Nếu $i = j$. Chỉ có một cách cắm $L[i,i]:= V[1,1]+V[2,2]+…+V[i,i]$
Nếu $i>j$. Không có cách cắm hợp lý
Nếu $i<j$. Có 2 trường hợp xẩy ra:
Cắm hoa $i$ vào lọ $j$. Tổng giá trị thẩm mỹ và làm đẹp là $L[i-1,j-1]+V(i,j)$. (Bằng tổng mức trước lúc cắm cộng với giá trị thẩm mỹ và làm đẹp khi cắm hoa $i$ vào lọ $j$)
Không cắm hoa $i$ vào lọ $j$ (hoàn toàn có thể cắm vào lọ trước $j$), giá trị thẫm mỹ của cách cắm là như cũ: $L[i,j-1]$

6.3. Cài đặt

L[i,j]:= -maxint; For i:=1 to k do For j:=i to n do If i = j then L[i,j]:=sum(i) else if i<j then L[i,j]:=max(L[i-1,j-1]+v[i,j],L[i,j-1]);

6.4. Một số bài toán khác

Câu lạc bộ

Bài toán

Có $n$ phòng học chuyên đề và $k$ nhóm học được đánh số thứ tự từ nhỏ đến lớn. Cần xếp $k$ nhóm trên vào $n$ phòng học sao cho nhóm có số hiệu nhỏ được xếp vào phòng có số hiệu nhỏ, nhóm có số hiệu lớn phải được xếp vào phòng có số hiệu lớn. Với mỗi phòng có chứ học viên, những ghế thừa phải được chuyển ra hết, nếu thiếu ghế thì lấy vào cho đủ ghế. Biết phòng $i$ có $A_i$ ghế, nhóm $j$ có $B_j$ học viên. Hãy chọn một phương án sắp xếp sao cho tổng số lần chuyển ghế ra và vào là tối thiểu.

Hướng dẫn

Khi xếp nhóm $i$ vào phòng $j$ thì số lần chuyển ghế đó đó là độ chênh lệch giữa số ghế trong phòng $i$ và số học viên trong nhóm. Đặt $V[i,j]:=|A_i – B_j|$

Mua giày (Đề QG bảng B năm 2003)

Bài toán

Trong hiệu có $n$ đôi giày, đôi giày $i$ có kích thước $H_i$. Có $k$ người cần mua giày, người $i$ cần mua đôi giày kích thước $S_i$. Khi người $i$ chọn mua đôi giày $j$ thì độ lệch sẽ là $|H_i-S_j|$. Hãy tìm cách chọn mua giày cho $k$ người trên sao cho tổng độ lệch là tối thiểu. Biết rằng từng người chỉ mua 1 đôi giày và 1 đôi giày cũng chỉ có một người tiêu dùng.

Hướng dẫn

Lập công thức giải như bài Câu lạc bộ. Chú ý chứng tỏ tính đúng đắn của bổ đề heuristic sau: Cho 2 dãy tăng dần những số dương $A_1, A_2, …, A_N$, $B_1, B_2, …, B_N$. Gọi $C_1, C_2, …, C_N$ là một hoán vị bất kỳ của dãy $B$. Khi đó: $|A_1-B_1| + |A_2-B_2| + … + |A_N-B_N| le |A_1-C_1| + |A_2 – C_2| + … + |A_N-C_N|$

7. Di chuyển

Cho bảng $A$ gồm $M * N$ ô. Từ ô $(i,j)$ hoàn toàn có thể di tán sang 3 ô $(i+1,j)$, $(i+1,j-1)$ và $(i+1,j+1)$. Hãy xác lập một lộ trình đi từ hàng 1 đến hàng $M$ sao cho tổng những ô trải qua là lớn số 1.

7.2. Công thức

Gọi $F(i,j)$ là giá trị lớn số 1 đã có được khi di tán đến ô $(i,j)$. Có 3 ô hoàn toàn có thể đi đến ô $(i,j)$ là $(i-1,j)$, $(i-1,j-1)$ và $(i-1,j+1)$. Do đó ta có công thức QHĐ như sau:

$F[1,j]=A[1,j]$
$F[i,j]=max(F[i-1,j],F([i-1,j-1],F[i-1,j+1])+A[i,j]$ với $i>1$

7.3. Cài đặt

Bảng phương án là bảng 2 chiều $F[0..m,0..n]$. (Tất cả những ô trên biên đều cho giá trị bằng 0).

Quá trình tính như sau:

for i:=1 to m do for j := 1 to n do F[i,j]=max(F[i-1,j],F[i-1,j-1],F[i-1,j+1]]+A[i,j]);

Cách setup này cho độ phức tạp bộ nhớ và thời hạn đều là $O(n^2)$. Ta hoàn toàn có thể tiết kiệm chi phí không khí nhớ bằng phương pháp tính trực tiếp trên mảng $A$.

7.4. Một số bài toán khác

Tam giác (IOI 1994)

Bài toán

Cho một tam giác gồm những số nguyên không âm. Hãy tính tổng lớn số 1 những số trên lối đi từ đỉnh tam giác xuống một điểm nào đó ở đáy tam giác nào đó. Tại mỗi ô ta chỉ có đi thẳng xuống, sang ô bên trái hoặc bên phải.

Hướng dẫn

Mô tả những thành phần của tam giác số như một ma trận, $A[i,j]$ là thành phần thứ $j$ trên dòng $i$ (với $1 le i le N$ và $1 le j le i$). Có 2 ô hoàn toàn có thể di chưyển đến ô $(i,j)$ là ô $(i-1,j-1)$ và ô $(i-1,j)$. Gọi $F(i,j)$ là tổng lớn số 1 hoàn toàn có thể có khi đi đến ô $(i,j)$ ta có:

$F[1,1]=A[1,1]$
$F[i,1]=F[i-1,1]+A[i,1]$
$F[i,j]=max( F[i-1,j-1],F[i-1,j] ) + A[i,j]$