VOI 10 Bài 1 - Dãy con chung không liền kề dài nhất

Xem dạng PDF
Gửi bài giải
Điểm: 0,08 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
VOI 2010
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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, \dots, i_{k - 1} < i_{k} - 1~;

~c_{1}~ = ~a_{i_1}~, ~c_{2}~ = ~a_{i_2}~, ..., ~c_{k}~ = ~a_{i_k}~.

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}, \dots, a_{m}~

và

B = ~b_{1}, b_{2}, \dots, 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.

Input

  • 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.

Output

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.

Sample Input

4 5
4
9
2
4
1
9
7
3
4

Sample Output

2

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    vominhmanh10  đã bình luận lúc 30, Tháng 12, 2025, 13:54

    ta lại dp nó có vẻ như kết hợp giữa xâu con chung dài nhất và chọn số phần tử không kề nhau dài nhất dp[i][j] = đoạn chung dài nhất khi tính tới phần tử thứ i của dãy a và thứ j của dãy b
    trường hợp a[i] == b[j]: bạn quyết định chọn nó thì chọn dp[i - 2][j - 2] và +1, ko chọn thì lấy dp[i - 1][j - 1], lấy giá trị tối ưu
    ngược lại: lấy giá trị tối ưu giữa dp[i - 1][j] hoặc dp[i][j - 1] 

    #include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define IO ios::sync_with_stdio(0); cin.tie(0)
const ll maxn = 1e6 + 5, inf = 1e18;
ll n, m, dp[1001][1001], a[maxn], b[maxn];
int main() {
    IO; cin >> m >> n;
    for (int i = 0; i < m; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i - 1] == b[j - 1]) dp[i][j] = max(dp[i - 1][j - 1], dp[i - 2][j - 2] + 1);
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[m][n];
}

  • -20
    phannam310810  đã bình luận lúc 23, Tháng 7, 2025, 2:58

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -41
    iamqazolp  đã bình luận lúc 21, Tháng 8, 2022, 13:36

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 26
    CODING  đã bình luận lúc 13, Tháng 8, 2021, 12:33

    Mn tham khảo ạ: https://www.youtube.com/watch?v=gODYcMfeLkY&t=322s