LNACS - VOI10 - Dãy con chung không liền kề dài nhất
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Dãy C = c 1 , c 2 , ..., c k là dãy con không liền kề của dãy A = a 1 , a 2 , ..., a m nếu C có thể nhận được bằng cách chọn một dãy các phần tử không liền kề của A, nghĩa là tìm dược dãy các chỉ số i 1 , i 2 , ..., i k sao cho:
1 ≤ i 1 , i 2 , ..., i k ≤ m;
i 1 < i 2 - 1, i 2 < i 3 - 1, ..., i k - 1 < i k - 1;
c 1 = a i1 , c 2 = a i2 , c k = a ik .
Ta gọi độ dài của dãy số là số phần tử của nó.
Cho hai dãy:
A = a 1 , a 2 , ..., a m
và
B = b 1 , b 2 , ..., b n
Dãy C được gọi là dãy con chung không liền kề của hai dãy A và B nếu như nó vừa là dãy con không liền kề của A, vừa là dãy con không liền kề của B.
Yêu cầu
Cho hai dãy số A và B. Hãy tìm độ dài của dãy con chung không liền kề dài nhất của hai dãy đã cho.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương m và n (2 ≤ m, n ≤ 10 3 ) được ghi cách nhau bởi dấu cách, lần lượt là số lượng phần tử của dãy A và dãy B.
- Dòng thứ i trong m dòng tiếp theo chứa số nguyên không âm a i (a i ≤ 10 4 ), i = 1, 2, ..., m.
- Dòng thứ j trong n dòng tiếp theo chứa số nguyên không âm b j (b j ≤ 10 4 ), j = 1, 2, ..., n.
Kết quả
Ghi ra trên một dòng duy nhất độ dài của dãy con chung không liền kề dài nhất của hai dãy A và B.
Ví dụ
Input: 4 5 4 9 2 4 1 9 7 3 4 Output: 2
- Người up: beo_chay_so
- Nguồn bài: VOI 2010