AstronomicalRecords

作者：寇煜杭

关键字：枚举 $dp$

题目简述

有若干个行星排成一行，这些行星只有大小这个属性。现在从中抽出$n$个行星，并将它们的大小比例按顺序记录在$A$数组。再从中抽出$m$个行星，并将它们的大小比例按顺序记录在$B$数组。现在给你$A，B$数组，问原行星至少要有多少个？($n,m<=50$)

解题思路

由于要求总行星最少，所以我们确定$A，B$包含了所有行星且公共行星尽量多。

因为$n$特别小，我们可以枚举$A$中某一行星和$B$中的某一行星是同一行星，然后将两数组转换为同一比例。现在转化为求$A,B$最大公共子序列。

我们用$f[i][j]$表示$A$数组前$i$个，$B$数组前$j$个的最大公共子序列。

转移：

$f[i][j]=max(f[i-1][j],f[i][j-1])$.

$if$ $(A[i]==B[j])$ $f[i][j]=max(f[i][j],f[i-1][j-1]+1)$.

最终答案就是对于每次枚举$n+m-f[n][m]$中的最小值.

时间复杂度$O((n*m)^2)$.