[AtCoder] Educational DP Contest F – LCS
問題
https://atcoder.jp/contests/dp/tasks/dp_f方針
いわゆる最長共通部分列問題ですね。有名なアルゴリズムなので、ググりましょう。
https://qiita.com/_rdtr/items/c49aa20f8d48fbea8bd2
http://www.cs.t-kougei.ac.jp/SSys/LCS.htmコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { string s, t; cin >> s >> t; int n = s.length(); int m = t.length(); int dp[n + 1][m + 1]{}; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (s[i] == t[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; } else { dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); } } } string ans = ""; int r = n; int c = m; while (r > 0 && c > 0) { if (s[r - 1] != t[c - 1]) { if (dp[r - 1][c] > dp[r][c - 1]) r--; else c--; } else { ans += s[r - 1]; r--; c--; } } reverse(ans.begin(), ans.end()); cout << ans << "\n"; return 0; } |