感觉这一类 DP 至少不应该被叫做“LCS模型”，本质应该是其他的东西......
先来考虑经典的 LCS：\(dp[n][m]\) 表示 \(S[n]\) 和 \(T[m]\) 匹配上的最长的长度。
那么我们不妨这样子考虑：假设有两个子序列自动机，一个是 \(S\) 的，另一个是 \(T\)的。
那么这玩意儿就能够解释成“最长的能够在两个自动机上都匹配得上的串的长度”。
看到这个题，这道题能够更好地解释这玩意儿。
\(dp[n][m]\) 表示 \(S[n]\) 和 \(T[m]\) 能否匹配得上。
那么我们对 \(S\) 和 \(T\) 可以根据新定义的“匹配”建立自动机，然后这个 DP 的本质就和上述一致了。
那么，根据“匹配”的规则转移即可，复杂度 \(O(m\sum|s_i|)\) 可以通过。
标签：匹配,题解,BSOJ7075,DP,自动机,dp From： https://www.cnblogs.com/lmpp/p/16822350.html