Trên hai đường thẳng song song L_1, L_2 người ta đánh dấu trên mỗi đường n điểm. Các điểm trên đường thẳng L_1 được đánh số 1, 2, …, n từ trái qua phải, còn các điểm trên đường thẳng L_2 được đánh số bởi d_1, d_2, …, d_n là một hoán vị của 1…n cũng được đánh dấu từ trái qua phải
Ta được phép nối điểm thứ i trên L_1 với điểm thứ j trên L_2 nếu |i – d_j| ≤ k .
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.
3 1 3 2 1
2
