Bắc cầu

Bắc cầu

Hai nước Anpha và Beta nằm ở hai bên bờ sông Omega, Anpha nằm ở bờ bắc và có M thành phố được đánh số từ 1 đến m, Beta nằm ở bờ nam và có N thành phố được đánh số từ 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ố thành phố của nước kia. Để tăng cường tình hữu nghị, hai nước muốn xây các 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à các cây cầu không được cắt nhau và mỗi thành phố chỉ là đầu 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 các thành phố của Anpha lần lượt là a1,a2,…am; các thành phố của Beta là b1,b2,...bn. Nếu thành phố ai và bj kết nghĩa với nhau thì coi ai “bằng” bj. Để các cây cầu không cắt nhau, nếu ta đã chọn cặp thành phố (ai,bj) để xây cầu thì cặp tiếp theo phải là cặp (au,bv) sao cho u > i và v > j. Như vậy các cặp thành phố được chọn xây cầu có thể coi là một dãy con chung của hai dãy a và b. Bài toán của chúng ta trở thành bài toán tìm dãy con chung dài nhất, ở đây hai phần tử “bằng” nhau nếu chúng có quan hệ kết nghĩa.