T1, T2의 각 노드에 서로 다른 번호가 부여되어 있다고 하자.
i번 노드의 자식들을 ci_1, ci_2, ...라고 하자.
ed[i][j]: i번 노드가 루트인 T1의 서브트리를 j번 노드가 루트인 T2의 서브트리로 바꾸는데 필요한 최소 편집 연산 수
ed[i][j]는 ed[ci_1..n][cj_1..m]들을 가지고 DP로 구할 수 있다.
dp[u][v]: ci_1..u 를 cj_1..v로 바꾸는데 필요한 최소 편집 연산 수
dp[u][v] = min(
dp[u-1][v] + (ci_u가 루트인 서브트리의 사이즈),
dp[u][v-1] + (cj_v가 루트인 서브트리의 사이즈),
dp[u-1][v-1] + ed[ci_u][cj_v])
그러면 ed[i][j]는 dp[n][m]이 된다.
시간복잡도는 $O(n^2)$
#include<cstdio> #include<vector> #include<algorithm> using namespace std; int tc, ed[2000][2000], sz[2000], pos, id; char la[2000], s[3001]; vector<int> adj[2000]; int f(int l, int r) { if (~ed[l][r]) return ed[l][r]; int n = adj[l].size(), m = adj[r].size(); vector<vector<int> > dp(n + 1, vector<int>(m + 1)); for (int i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + sz[adj[l][i - 1]]; for (int i = 1; i <= m; i++) dp[0][i] = dp[0][i - 1] + sz[adj[r][i - 1]]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) dp[i][j] = min({ dp[i][j - 1] + sz[adj[r][j - 1]], dp[i - 1][j] + sz[adj[l][i - 1]], dp[i - 1][j - 1] + f(adj[l][i - 1], adj[r][j - 1]) }); return ed[l][r] = dp[n][m] + (la[l] != la[r]); } void gen() { int h = id++, st = pos; adj[h].clear(); la[h] = s[++pos]; while (s[++pos] != ')') adj[h].push_back(id), gen(); sz[h] = (pos - st) / 3 + 1; } void solve() { fill(&ed[0][0], &ed[1999][2000], -1); scanf("%s", s); id = pos = 0; gen(); int t = id; scanf("%s", s); pos = 0; gen(); printf("%d\n", f(0, t)); } int main() { for (scanf("%d", &tc); tc--;) solve(); return 0; }
