Lãnh Địa Cô Đơn : DP

Phần II: Các bài toán và áp dụng.

Quy hoạch động thường được chia làm 2 phần:

+ Trả lời:

- Khởi tạo.

- Tính toán dựa theo công thức truy hồi.

+ Truy vết: in ra cấu hình tối ưu.

II.1: LIS _ Khởi đầu của DP

1. Bài toán tổng quát.

LIS là từ viết tắt của Longest Increasing Subsequence LIS (dãy con tăng dài nhất ). Bài toán được phát biểu tổng quát như sau:

“ Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N].
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i₁],... A[i_k] thỏa mãn
i₁ < i₂ < ... < i_k và A[i₁] < A[i₂] < .. < A[i_k]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử? “

VD: Với dãy 1 2 6 5 8 9

Thì dãy tăng lớn nhất của nó sẽ là 1 2 5 8 9 hoặc 1 2 6 8 9

Bài toán có 2 cách giải phổ biến, 1 cách giải với độ phức tạp O(n^2) và một cách giải với độ phức tạp O(nlogn) – cái cách nlogn này có thể giải bằng nhiều kĩ thuật hỗ trợ như : BIT , IT , … Nhưng mình sẽ giới thiệu với các bạn cách sử dụng chặt nhị phân cách đơn giản nhất.

2. Cách 1: O(n^2) Quy hoạch động truyền thống.

Cách làm này mang tính cách mạng, nó sẽ giúp các bạn tiếp cận đến gần DP hơn là những ví dụ ở phần 1, không những thế cách làm này cũng khá cổ điển , mang tính đặc trưng của quy hoạch động cao.

Đầu tiên ta, ta sẽ nghĩ đến 1 việc , đó là :”làm thế nào để đưa A[i] vào 1 dãy con sao cho nó là kết thúc của dãy con đó”.

Giả sử phần tử cuối cùng của dãy con là A[j] , vậy khi đấy để A[i] là kết thúc của dãy con này thì :

+ j < i (đảm bảo tính thứ tự ).

+ A[j] < A[i] ( đảm bảo tính tăng).

VD :

I	1	2	3	4	5	6	7
A[i]	1	2	9	4	5	3	6

Dãy con kết thúc tại A[5] = 5 ( ví dụ dãy 1 2 4 5)

A[3] không thể là kết thúc của dãy này được vì 3 < 5.

A[6] không thể là kết thúc của dãy này vì A[6] < A[5].

A[7] có thể là kết thúc của dãy con này vì 7 > 5 && A[7] > A[5].

Do đó ta có công thức quy hoạch động đầu tiên.

Gọi LIS[i] là độ dài dãy con tăng dài nhất kết thúc tại vị trí i.

· Khi đó LIS[i] ban đầu sẽ bằng 1 ( vì nguyên phần từ thứ i cũng tính là 1 dãy tăng) – Đây chính là bước khởi tạo

Khi đó ta có: LIS [i] = max (LIS[j] + 1) ( 1 <= j < i && a[j] < a[i] ) – chính là điều kiện để i là kết thúc của 1 dãy con. à công thức truy hồi.

Kết quả sẽ là max (dp[i] ) (1 <= i <=n ) à Kết quả.

Source code:

int LIS(){

int ans = 0; lis[0] = 0;

for (int i=1;i<=n;++i) lis[i] = 1;

for (int i=1;i<=n;++i){

for (int j=1;j< i;++j){

if ( a[j] < a[i] )

lis[i] = max (lis[j] +1 , dp[i]); }

ans = max (ans , lis[i]);

}

return ans;

}

Độ phức tạp của thuật toán là O(N^2). Và theo source code thì độ dài dãy tăng lớn nhất sẽ là ans.

Tương tự nếu ta thay vì tìm dãy tăng ta tìm dãy giảm lớn nhất, ta cũng tính tương tự. chỉ khác ở công thức truy hồi :

LDS[i] = max (LIS[j] +1 ) (1 <= j < i && a[j] > a[i] )

Nếu đề bài hỏi :”Hãy in ra dãy tăng dài nhất của 1 dãy số ( thay vì độ dài nhất của nó)”

VD : dãy 1 2 4 2 6 à trả lời : 1 2 4 6.

Đây chính là phần truy vết của bài toán.

Thông thường truy vết ta sẽ làm ngược lại so với cách làm QHĐ.

Với bài toán trên

Đầu tiên ta sẽ tìm vị trí kết thúc của dãy tăng lớn nhất. Việc này khá đơn giản, ta chỉ cần tìm vị trí i sao cho LIS[i] = Kết quả à phần tử cuối cùng của dãy sẽ là A[i];

Sau đó chạy từ i à 1 và ta tìm j sao cho LIS[j] = LIS[i] + 1 && A[j] < A[i]

( tìm phần tử thứ 2 của dãy từ dưới lên ) sau đó gán i = j và tiếp tục tìm tiếp cho đến khi LIS[i] = 0; ( không còn phần tử nào nữa )

VD: dãy 1 2 4 2 5 5

Sau khi tính công thức quy hoạch động, ta có bảng sau:

I	1	2	3	4	5	6
LIS[i]	1	2	3	2	4	4

Dễ dàng nhận thấy kết quả = LIS[6] à ta sẽ tính vị trí thứ 6.

Đưa A[6] vào kết quả ta được mảng ans[] = {5};

Ta tìm LIS[j] = LIS[i] -1 ( j < I ) . Ta thấy LIS[3] thỏa mãn đều này và hơn thế nữa A[3] < A[6]. à đưa A[3] vào ans[] = {5,4} tìm tiếp từ A[3].

Thấy A[2] < A[3] && LIS[2] +1 = LIS[3] à đưa A[2] vào kết quả ans[] = {5,4,2}.

Tìm tiếp với A[2] à thấy LIS[1] + 1 = LIS[2] à nhét A[1] và dãy kết quả ans[] = {5,4,2,1} à ta đã hoàn thành truy vết rồi .

Source code:

void trace(){

// ans là dãy lưu kết quả truy vết

// res là độ dãi dãy tăng lớn nhất

int i = n, j;

int k = res;

for (int i=n;i >= 1 ;--i) if ( LIS[i] == res ) break;

ans[res] = a[i]; res = res - 1;

int j= i- 1;

while (LIS[i] != 1){

while ( j > 0 ){

if (LIS[j] + 1 == LIS[i] && a[j] < a[i]){

ans[res--] = A[j];

i = j--;

break;

}

j--;

}

for (int i=1 ;i <= k;++i) cout << ans[i] << ' ';

}

Độ phức tạp của truy vết là O(N).

Vậy là ta đã hoàn thành bài toán quy hoạch động cơ bản đầu tiên ^^.Sau đây mình xin đề cập đến 1 số ví dụ của bài toán này.

Bài toán 1: Tìm dãy con giảm dài nhất ( mình đã nói rồi )

Bài toán 2: Cho n người , mỗi người có 2 chỉ số p[i] – sức mạnh , b[i] – độ xinh đẹp. người ta chỉ xếp một số người vào 1 hàng gồm p người thỏa mãn

Với mỗi người i thì p-1 người còn lại mỗi người phải thỏa mãn(gọi tạm 1 người là i ) : nếu p[i] > p[j] thì b[i] < b[j] và ngược lại ( để cùng đẳng cấp -.- ).

Người ta muốn tìm ra hàng dài nhất có thể xếp (có nhiều người nhất ).

Nào bây giờ bạn hãy thử nghĩ 1 tí đi , tạm thời gạt bài viết này sang 1 bên và suy nghĩ đi ạ . Và một lúc sau hãy quay lại và so với đáp án của mình nhé !!!!

Cách giải của mình rất đơn giản:

Đầu tiên ta sort lại mảng theo chỉ số p[i] , bây giờ ta có:

p[1] < p[2] <… < p[n].Chẳng phải nhiệm vụ của mình bây giờ chính là tìm dãy con giảm dài nhất theo chỉ số b[i] sao. (gọi kết quả là k)

Khi đó dãy cần tìm sẽ là k người i1 < i2 < i3< … < ik và

P[i1] < P[i2] <.. .< P[ik].

B[i1] > B[i2] > … > B[ik].

Độ phức tạp quy hoạch động:O(n^2) , độ phức tạp truy vết O(N).

Bonus bài toán 2.1:

Cho một trung tâm thể thao gồm n người , mỗi người vẫn sẽ có 2 chỉ số p[i] và b[i]. Nhưng thay vì cùng đẳng cấp , lại có một số người lại sinh tính đố kị nhau.

Người I đố kị người j khi p[i] < p[j] && b[i] > b[j] và ngược lại.

Thật không may, trung tâm lại sắp tổ chức 1 yến tiệc, và để giảm thiểu tai nạn đáng tiếc , trung tâm quyết định không mời những người đố kị nhau.

Bạn đang rất đói tiền, và bạn muốn kiếm được chút tiền nên đánh liều tính mạng của mình bằng cách làm người viết thiệp mời. Và nhiệm vụ của bạn là mời được nhiều người nhất có thể và không ai trong số họ đố kị nhau. Hãy in ra kết quả đó.

Bài toán 3: Bây giờ, sau khi sống sót sau vụ Dự tiệc , bạn lại đi làm viêc cho 1 gia chủ kì lạ . Ông ta rất tàn bạo nhưng lại vô cùng yêu toán học. Ông ấy đưa bạn 1 bài toán : “ Cho 1 dãy N số , hãy tìm 1 dãy số đẹp” – và ông ấy chẳng nói gì cả (Như kiểu muốn giết bạn vậy) rất may , bạn tìm được quy luật của dãy số là một phần của dãy số tăng , còn phần còn lại thì giảm . VD dãy 1 2 5 4 2 là 1 dãy thỏa mãn khi 1 2 5 tăng còn 5 4 2 lại giảm. Tìm ra 1 dãy còn chưa đủ. Ông ta còn muốn hành hạ bạn nếu ông ấy tìm ra dãy nào dài hơn thế. Bạn đang rất bối rối, nhưng với chiếc siêu máy tính mà bạn đã bán cả nhà để mua trong tay – bạn hãy tìm ra 1 dãy số để không bị ông ta ăn hành

Gợi ý: Bài này bạn chỉ cần xây 2 mảng LIS[i] là dãy tăng lớn nhất kết thúc tại i và LDS[i] là dãy giảm dài nhất bắt đầu tại i. Kết quả bài toán sẽ là

MAX (LIS[i] + LDS[i] – 1). ( trừ 1 vì i được tính 2 lần ) và sau đó ta tiến hành truy vết để tìm ra kết quả.

Bonus Bài toán 3.1 : Một dãy số được gọi là zigzac khi nó mang tính tăng giảm xen kẽ , VD : 1 5 4 6 5 7 hoặc 4 2 3 1 6 là các dãy thỏa mãn . Nhưng dãy 1 2 4 3 5 4 6 lại không.

Cho bạn 1 dãy N số hãy tìm độ dài dãy zigzac lớn nhất .

Đã kết thúc phần II.1.1 rồi hí hí , bây giờ mình sẽ bonus cho các bạn một vài bài để sub và để nghĩ

+ https://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493 – Zigzac

+ http://vn.spoj.com/problems/LIQ/ - LIS bản siêu dễ.

+ http://acm.sgu.ru/problem.php?contest=0&problem=199 – bài toán 2.1

+ https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2890

Có gì không hiểu các bạn có thể mail cho mình , mình sẽ giải thích rõ hơn và sửa lại bài , nếu cần thiết, cảm ơn các bạn đã đọc bài này.