CVBB ACM Team

--- 2020-2021:teams:legal_string:jxm2001:dp套dp [2021/08/25 21:15]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:dp套dp [2021/08/25 22:05] (当前版本)
jxm2001
@@ 行 13: / 行 13: @@
 === 题意 ===
-给定一个长度为 $n$ 的字符串 $S$。对 $i=0\sim n$，求有多少长度为 $m$ 的 $T$ 满足 $\text{LCS}(S,T)=i$。其中 $S,T$ 只含 $\text{ATGC}$。
+给定一个长度为 $n$ 的字符串 $S$。对 $i=0\sim n$，求有多少长度为 $m$ 的 $T$ 满足 $\text{LCS}(S,T)=i$。其中字符集为
+ $\text{ATGC}$。
 === 题解 ===
@@ 行 116: / 行 117: @@
 </hidden>
+==== 例题二 ====
+[[https://www.luogu.com.cn/problem/P4590|洛谷p4899]]
+=== 题意 ===
+给定一个长度为 $n$ 的字符串 $S$。对 $i=0\sim n$，求有多少长度为 $m$ 的 $T$ 满足 $\text{LCS}(S,T)=i$ 且 $T$ 不含 $\text{NOI}$ 子串。其中字符集为 $\text{NOI}$。
+=== 题解 ===
+模拟 $\text{KMP}$ 记录 $T$ 与 $\text{NOI}$ 的匹配情况即可，也是一个自动机，本题该状态可任意放在内/外层 $\text{dp}$ 维护。但是状态比较复杂时建议放在内层维护。