Hướng dẫn giải của Atcoder Educational DP Contest F - LCS

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: NoobCpp

Đầu tiên hãy đọc link này, sau đó giải quyết bài toán theo mô hình ~dp~, rồi truy vết ngược lại tìm đáp án.

Độ phức tạp thuật toán: ~O(N ^ 2)~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}

int dp[3001][3001];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    string s, t; cin >> s >> t;
    int n = s.size(), m = t.size();

    for(int i = 0 ; i <= n; ++i) {
        for(int j = 0; j <= m; ++j)  {
            if(!i || !j) dp[i][j] = 0;
            else if(s[i - 1] == t[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    string ret = "";

    while(n && m) {
        if(s[n - 1] == t[m - 1]) {
            ret += s[n - 1];
            n--;
            m--;
        }
        else if(dp[n - 1][m] > dp[n][m - 1]) n--;
        else m--;
     }

     reverse(ret.begin(), ret.end());

     cout << ret << endl;
}

Bình luận

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


  • 6
    MaiThanh1342  đã bình luận lúc 16, Tháng 7, 2024, 3:01 ← chỉnh sửa

    Liên kết wiki bên trên:

    https://wiki.vnoi.info/algo/dp/basic-dynamic-programming-2.md#141-x%C3%A2u-con-chung-d%C3%A0i-nh%E1%BA%A5t:~:text=1.4.1.%20X%C3%A2u%20con%20chung%20d%C3%A0i%20nh%E1%BA%A5t


  • -18
    Tri  đã bình luận lúc 19, Tháng 2, 2023, 5:44

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