Warning: session_start(): open(/tmp/sess_08cb9a57f25561317885e49662f095c9, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== $\text{dp}$ 套 $\text{dp}$ ======
===== 算法简介 =====
把 $\text{dp}$ 当作内层状态进行转移。
===== 算法例题 =====
==== 例题一 ====
[[https://acm.dingbacode.com/showproblem.php?pid=4899|HDU4899]]
=== 题意 ===
给定一个长度为 $n$ 的字符串 $S$。对 $i=0\sim n$，求有多少长度为 $m$ 的 $T$ 满足 $\text{LCS}(S,T)=i$。其中字符集为
$\text{ATGC}$。
=== 题解 ===
首先 $\text{LCS}$ 的经典算法，设 $\text{dp}(i,j)=\text{LCS}(T[1\sim i],S[1\sim j])$，于是有
$$
\text{dp}(i,j) =
\begin{cases}
\text{dp}(i-1,j-1)+1, & T[i] = S[j] \\
\max(\text{dp}(i-1,j),\text{dp}(i,j-1)), & T[i]\neq S[j]
\end{cases}
$$
固定 $S$，不难发现 $\text{dp}(i,\ast)$ 的结果只与 $\text{dp}(i-1,\ast)$ 以及 $T[i]$ 相关。
不妨考虑状态表示 $\text{dp}(i,\ast)$ 数组。这是一个一维数组，且 $0\le \text{dp}(i,j)-\text{dp}(i,j-1)\le 1$，因此可以通过差分用一个二进制数表示状态。
考虑处理出 $\text{dp}(i-1,\ast)\to \text{dp}(i,\ast)$，其中转移边为 $T[i]=\text{ATGC}$，这是一个自动机。
设 $\text{f}(i,j)$ 表示所有长度为 $i$ 状态为 $j$ 的 $T$ 的数量，利用自动机进行状态转移即可。总时间复杂度 $O(|\sum|2^nm)$。
const int MAXB=15,MAXN=20,mod=1e9+7;
int a[MAXN],b[MAXN],c[MAXN],nxt[1<>=1;
}
}
int encode(int n){
int p=0;
for(int i=n;i;i--){
c[i]-=c[i-1];
p<<=1;
p+=c[i];
}
return p;
}
void add(int &a,int b){
a+=b;
a%=mod;
}
void solve(){
scanf("%s",s+1);
int n=strlen(s+1),m=read_int();
_rep(i,1,n){
if(s[i]=='A')
a[i]=0;
else if(s[i]=='G')
a[i]=1;
else if(s[i]=='T')
a[i]=2;
else
a[i]=3;
}
int S=1<
==== 例题二 ====
[[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}$ 维护。但是状态比较复杂时建议放在内层维护。