DPまとめコンテスト F - LCS

F - LCS

概要

英小文字からなる文字列がある。
の最長共通部分列(Longest Common Subsequence)を求めよ。

制約

方針

次のステップで求める。

1. のLCSの長さをDPで求める。
2. 上記のDP配列よりLCSを復元する。復元方法としてはDP配列が更新されたタイミングの文字を追加してゆく。

感想

最初はDP配列にLCSを全部持たせてましたが、MLEやらREやらでうまくいきませんでした。
Submission #3942127 - Educational DP Contest / DP まとめコンテスト

解答

Submission #3952280 - Educational DP Contest / DP まとめコンテスト

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	string s, t;
	cin >> s >> t;
 
	int n, m;
	n = s.length();
	m = t.length();
 
	int dp[n+1][m+1];
	// dp[i][j] : sのi文字目、tのj文字目のLCSの長さ
	rep(i, n+1) rep(j, m+1) dp[i][j] = 0;
 
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(s[i-1] == t[j-1]){
				dp[i][j] = dp[i-1][j-1] + 1;
			}else{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
 
	// dp配列を逆からたどってLCSを作成する
	// LCSの長さが更新されたときの文字を追加していく
 
	string ans = "";
	int x = n;
	int y = m;
	while(x > 0 && y > 0){
		if(dp[x][y] == dp[x-1][y]){
			x--;
		}else if(dp[x][y] == dp[x][y-1]){
			y--;
		}else{
			x--;
			y--;
			ans.push_back(s[x]);
		}
	}
 
	reverse(ans.begin(), ans.end());
	cout << ans << endl;
}