Đây là một bài quy họch động đơn giản. Lời giải dựa trên tính chất for trâu của máy tính để giải quyết vấn đề

Gọi xâu con chung dài nhất tính đến phần tử i của xâu A và phần tử j của xâu B là C[i][j]

Chúng ta sẽ lần lượt đi so sánh hai xâu

Giả sử ta đang xét đến hai phần tử A[i] và B[j]

Nếu A[i] = B[j]

C[i][j] = C[i-1][j-1] + 1

Nếu A[i] ≠ B[j]

C[i][j] = max (C[i-1][j],C[i][j-1])

Xếp hình?

Lời nói đầu

Trong series báo cáo này, (chúng) tôi sẽ trình bày một vấn đề, không hẳn là một “thuật toán” mà là một bài toán: làm sao để bao phủ một mặt phẳng bằng hình vẽ cho trước. Dạng tổng quát của bài toán này là NP-khó, nhưng trong một số trường hợp thì ta vẫn có những lỗi đi riêng nhờ sự trợ giúp của máy tính.

Bài 1

Cho một mạng lưới hình vuông cạnh 2ⁿ mà mỗi ô vuông có cạnh là 1. Hãy bao phủ mạng lưới trên bằng hình vẽ sau, biết rằng có một ô nào đó được để trống.

Trong đó:

n – độ dài của mạng lưới

x,y – tọa độ của ô để trống

Ý tưởng:

Nếu mạng lưới được bao phủ hết bằng hình trên, thì chắc hẳn số ô của mạng lưới phải chia hết cho 3

Thật vậy, 2ⁿx2ⁿ – 1 = (4-1)(4^n-1 + 4^n-2 + … + 4 + 1) chia hết cho 3

Tiếp theo, chúng ta sẽ giải quyết vấn đề "lấp kín các ô còn lại trong mạng lưới". Hãy chia mạng lưới làm 4 mạng lưới vuông nhỏ hơn bằng nhau

Dễ dàng nhận thấy nếu n = 1, ta luôn có đáp số cho bài toán. Trước khi đến với dạng tổng quát, ta cần đi qua trường hợp n = 2

Giả sử rằng ô vuông cần được để "trống" là một trong những ô trong hình kia, ta có thể có nhiều cách chọn khác nhau mà vẫn giải quyết được bài toán

Với trường hợp tổng quát, ta có thể "sử dụng" 3 hình trên để giải hết tất cả các trường hợp của n.

Bài 2

Cho một mạng lưới hình vuông có cạnh (6N+1). Hãy bao phủ mạng lưới trên bằng hình vẽ sau, biết rằng có một ô nào đó được để trống.

Trong đó:

n - độ dài của mạng lưới theo yêu cầu

x, y - tọa độ của ô để trống

Ý tưởng:

Đầu tiên, ta xét với trường hợp N=1 nhỏ nhất

Bằng các phép đối xứng, xoay hình, ta có thể giải được tất cả những bài toán N=1 bằng 3 hình trên.

Giả sử, ta biết làm thế nào để lát mạng lưới vuông cạnh 6N+1, ta sẽ thử tìm cách lát mạng lưới vuông cạnh 6N+7

Dễ dàng thấy rằng, hình vuông (6N+1) x (6N+1) nhỏ hơn hình vuông (6N+7) x (6N+7) nên ta sẽ chia hình 6N+7 thành hình nhỏ như sau

Và cuối cùng, phần "thừa" ở góc phải trên của hình chính là bài toán với N = 1 ban đầu.

//Last edit: Tập tin nội bộ trường chuyên KHTN, tham khảo acm.sgu.ru ; ACM ICPC 1997 ; Bugs CEOI 2002 ; IOI 2005 ; CSP 1993 ; ...

Full post đăng tải trên minhtt159.wordpress.com

Nguồn : Tin Tuyển 2013 (Trần Tuấn Minh - Nguyễn Mạnh Cường - Nguyễn Hoàng Long)

Bấm cái gì :| Lười thế. Có mỗi "for trâu" thôi mà cũng giở Solution ra. Ra chống đẩy 10 cái xong làm tiếp bài khác.

Ngoài ra thì còn "thuật toán" đảo ngược số khá "quan trọng" cho những bạn nào không biết

int reverseNumber(A):
     int B = 0
     while A > 0: 
          B = B*10 + A%10 //Lấy số cuối của A đặt vào số đầu của B
          A = A/10        //Xóa số cuối của A
     endwhile
     return B

Theo đề bài, ta gọi F[i] là thời gian tối ưu của dãy i người

Bằng suy luận, ta thấy rằng nếu người "i" đi ra khỏi hàng là cách tối ưu khi và chỉ khi

R[i-1] + F[i-2] (giá của việc người "i" đi ra khỏi hàng) nhỏ hơn T[i] + F[i-1] (giá của việc người "i" đứng lại trong hàng)

Như vậy, ta có Pseudo Code

F[0] = 0    //Thời gian tổng của dãy có 0 người
F[1] = T[1] //Thời gian tổng của dãy có 1 người duy nhất
for i = 2 -> N:
    F[i] = min (F[i-1] + T[i] và F[i-2] + R[i-1])
endfor

Giới Thiệu

LIS là một bài toán tìm một dãy con trong một tập các phân tử, mà các phần tử trong dãy con được sắp xếp theo thứ tự (nhỏ đến lớn) mà dãy con này dài nhất có thể. Dãy con này không cần thiết phải liền kề, hoặc là duy nhất. Bài toán dãy con tăng dài nhất được áp dụng rộng rãi ở nhiều lĩnh vực: Toán học (thuật toán, lý thuyết ma trận, lý thuyết đại diện) hay Vật Lý. Thuật toán LIS giải trong độ phức tạp O(n*logn) với "n" là độ dài của dãy phần tử cho trước.

Ví dụ

Một dãy cho trước như sau

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

Dãy con tăng dài nhất trong chuỗi số trên có độ dài 6 phần tử

0, 2, 6, 9, 11, 15

Nhưng dễ dàng thấy rằng, dãy này không phải là duy nhất, ngoài ra còn những dãy khác cũng thỏa mãn là dãy con tăng dài nhất

0, 4, 6, 9, 11, 15 hoặc 0, 4, 6, 9, 13, 15

Thuật toán

Thuật toán của bài toán LIS này được giải quyết hiệu quả với độ phức tạp O(N*logN) qua việc sự dụng mảng và tìm kiếm nhị phân. Thuật toán xét lần lượt các phần tử, duy trì LIS đã tìm được tính tới thời điểm đang xét.

Giả sử kí hiệu các tập con là A[0] , A[1] , ... thì sau khi xử lý tập A[i], thuật toán sẽ lưu lại 2 mảng:

• M[j] : lưu số (thứ tự) "k" của tập A mà dãy con đó thỏa mãn tính chất và có độ dài j, với:
  • j là độ dài của dãy con tăng dài nhất tính tới thời điểm i
  • k là phần tử cuối của dãy con tăng tính tới thời điểm i
• P[k] : lưu số (thứ tự) đằng trước số k trong dãy con tăng dài nhất (mà kết thúc là số k)

Ngoài ra ta có thể lưu thêm một biến L là độ dài của dãy con tăng dài nhất mà ta đã tìm được

Lưu ý rằng, tại mọi thời điểm trong khi xét, dãy A[M[0]] , A[M[1]] ,... A[M[L]] là một dãy không giảm. Nếu có một dãy con tăng có độ dài i (kết thúc tại A[M[i]]) thì cũng có một dãy con tăng khác độ dài i-1 (kết thúc tại A[P[M[i]]])

Pseudo Code

mảng P : dãy có độ dài N
mảng M : dãy có độ dài N+1
biến L = 0

for i = 0 -> N-1:
    //Chặt nhị phân để tìm số j lớn nhất sao cho j ≤ L mà A[M[j]] < A[i]
    đầu = 1
    cuối = L
    while đầu ≤ cuối:
        giữa = giá trị nguyên của (đầu + cuối) / 2
        if A[M[giữa]] < A[i]:
            đầu = giữa + 1
        else:
            cuối = giữa - 1
        endif
    endwhile

    //Sau khi chặt nhị phân, "đầu" lớn hơn so với độ dài của dãy liền trước A[i]
    Lmới = đầu

    //Gán giá trị liền trước của dãy bằng số Lmới-1
    P[i] = M[Lmới-1]
    M[Lmới] = i;

    if Lmới > L:
        L = Lmới //do ta đã tìm được dãy con tăng có độ dài dài hơn dãy con tăng cũ
    endif
endfor

// Dựng lại dãy con tăng
mảng S : độ dài L
k = M[L]
for i = L-1 -> 0:
    S[i] = A[k]
    k = P[k]
endfor

Nguồn: Wikipedia