Editorial for Atcoder Educational DP Contest F - LCS

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 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;
}

Comments

Please read the guidelines before commenting.

3

MaiThanh1342 commented on July 16, 2024, 3:01 a.m.

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

-16

This comment is hidden due to too much negative feedback. Show it anyway.