dp套dp学习笔记

1 dp 和 dp套dp

  • dp 套 dp 中的 dp 一定是 dp 套 dp 的基础,而 dp 套 dp 也就是从 dp 的基础上 dp 而来的。
  • 没错,上面这句话就是套娃。

为了方便大家理解,从这句话开始,dp套dp 将作为一个不加空格的词,方便区分。

dp 的时候,我们一般会设计一个 dp 状态,然后让 dp 从某个状态向某个状态转移,最终统计某些状态最终的值。

而在 dp套dp 里面,我们就将内层 dp 的结果作为外层 dp 的状态进行 dp。

2 正片

举个例子:

  • 例 \(1\)

  • 求长度为 \(n\),字符集为 \(\texttt{N},\texttt{O},\texttt{I}\),与给定字符串 \(S\) 的 \(\text{LCS}\) 为 \(len\) 的字符串数量。
  • \(|S|\leq15\),\(n\leq10^3\)

2.1 \(\text{LCS}\) 回顾

显然对于字符串 \(A\) 和 \(B\),我们记 \(\text{LCS}_{x,y}\) 为 \(A\) 前 \(x\) 位,\(B\) 前 \(y\) 位的最长公共子序列长度,则

\[\text{LCS}_{x,y}=\left\{ \begin{aligned} \text{LCS}_{x-1,y-1}+1&&A_x=B_y\\ \max\{\text{LCS}_{x-1,y},\text{LCS}_{x,y-1}\}&&A_x\neq B_y\\ \end{aligned} \right.\]

2.2 转化

第一部分最后一句中,我们提到外层 dp 的状态就是内层 dp 的结果,于是一个最暴力的想法就是记录所有 \(\text{LCS}\) 作为状态。

  • 小补充:dp套dp 中内层的转移应该是一个自动机的状态,但是笔者对自动机理解不深,所以本文仍然用“状态”和“转移”描述自动机的边。

此时,我们要记录的是长度为 \(i\),和 \(S\) 的 \(\text{LCS}\) 为某个数组的字符串数量。

然而我们发现,如果我们在某个字符串后面加一个新的字符,只会新生成一行 \(\text{LCS}\),而这一行 \(\text{LCS}\) 完全通过上一行生成!

(配图,咕了)

于是我们只要记录 \(\text{LCS}\) 最后一行为某个数组的字符串数量了。

然后我们还发现 \(\text{LCS}_{x+1,y}-\text{LCS}_{x,y}\) 只能是 \(0\) 或者 \(1\),于是我们还能差分最后一行得到一个 \(01\) 字符串并再次状压。

于是我们就能写出很优美的 dp套dp 了。

算法复杂度 \(\text O(\large2^{|S|}m|\Sigma|)\)

  • 示例代码(可以通过该题)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x;
}
const int p=1000000007;
int nxt[100003][4],f[2][100003],ans[1003];
char s[23];
const char ch[4]={'A','T','C','G'};
void solve()
{
	scanf("%s",s+1);
	int n=strlen(s+1),m=read(),st=1<<n;
	for(int i=0,tmp[23],res[23]; i<st; ++i) 
	{
		res[0]=tmp[0]=0;
		for(int j=1,k=i; j<=n; ++j,k>>=1) tmp[j]=tmp[j-1]+(k&1);
		for(int k=0,num; k<4; ++k)
		{
			num=0;
			for(int j=1; j<=n; ++j) res[j]=(s[j]==ch[k])?tmp[j-1]+1:max(tmp[j],res[j-1]),num+=(1<<(j-1))*(res[j]-res[j-1]);
			nxt[i][k]=num;
		}
	}
	memset(f,0,sizeof(f));
	f[0][0]=1;
	for(int i=0; i<m; ++i)
	{
		for(int j=0; j<st; ++j) f[(i&1)^1][j]=0;
		for(int j=0; j<st; ++j) for(int k=0; k<4; ++k) (f[(i&1)^1][nxt[j][k]]+=f[i&1][j])%=p;
	}
	for(int i=0; i<=n; ++i) ans[i]=0;
	for(int i=0; i<st; ++i) (ans[__builtin_popcount(i)]+=f[m&1][i])%=p;
	for(int i=0; i<=n; ++i) printf("%lld\n",ans[i]);
}
signed main()
{
	for(int T=read(); T--;) solve();
	return 0;
}

2.4 小试牛刀

  • 例 \(2\)

  • 求长度为 \(n\),字符集为 \(\texttt{N},\texttt{O},\texttt{I}\),不包含子串 \(\texttt{NOI}\) 的字符串中,与给定字符串 \(S\) 的 \(\text{LCS}\) 为 \(len\) 的字符串数量。
  • \(|S|\leq15\),\(n\leq10^3\)

同步记录是否有后缀是 \(\tt{N},\tt{NO}\) 即可。

  • 示例代码(可以通过该题)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x;
}
const int p=1000000007;
int nxt[100003][3],f[2][100003][3],ans[1003];
char s[23];
const char ch[3]={'N','O','I'};
signed main()
{
	int m=read(),n=read(),st=1<<n;
	scanf("%s",s+1);
	for(int i=0,tmp[23],res[23]; i<st; ++i) 
	{
		res[0]=tmp[0]=0;
		for(int j=1,k=i; j<=n; ++j,k>>=1) tmp[j]=tmp[j-1]+(k&1);
		for(int k=0,num; k<3; ++k)
		{
			num=0;
			for(int j=1; j<=n; ++j) res[j]=(s[j]==ch[k])?tmp[j-1]+1:max(tmp[j],res[j-1]),num+=(1<<(j-1))*(res[j]-res[j-1]);
			nxt[i][k]=num;
		}
	}
	memset(f,0,sizeof(f));
	f[0][0][0]=1;
	for(int i=0; i<m; ++i)
	{
		for(int j=0; j<st; ++j) f[(i&1)^1][j][0]=f[(i&1)^1][j][1]=f[(i&1)^1][j][2]=0;
		for(int j=0; j<st; ++j) 
		{
			(f[(i&1)^1][nxt[j][0]][1]+=f[i&1][j][0]+f[i&1][j][1]+f[i&1][j][2])%=p;
			(f[(i&1)^1][nxt[j][1]][0]+=f[i&1][j][0]+f[i&1][j][2])%=p;
			(f[(i&1)^1][nxt[j][1]][2]+=f[i&1][j][1])%=p;
			(f[(i&1)^1][nxt[j][2]][0]+=f[i&1][j][0]+f[i&1][j][1])%=p;
		}
	}
	for(int i=0; i<=n; ++i) ans[i]=0;
	for(int i=0; i<st; ++i) (ans[__builtin_popcount(i)]+=f[m&1][i][0]+f[m&1][i][1]+f[m&1][i][2])%=p;
	for(int i=0; i<=n; ++i) printf("%lld\n",ans[i]);
	return 0;
}

3 你已经学会基本操作了,接下来请A掉这道题

首先,请和我一起虔诚地膜拜 zhouAKngyang,因为他一年前在考场上就爆切了这道题。

此题中,内层 dp 也比较难想,我们先考虑内层 dp,即给你一些牌,判断有没有和。

  • zhouAKngyang:你先想一会,不要马上看题解。

可惜以 delta_X 的实力想 114514 年还是不会……

首先,不难发现我们只需要知道编号为 \(x\) 的牌的数量,不妨把一些牌的集合记为每种牌的出现次数,例如 \(\{1,1,1,2,3,4,5,6,7,8,9,9,9\}\) 记为 \(\{3,1,1,1,1,1,1,1,3\}\),第 \(i\) 张牌的出现次数为 \(cnt_i\)。

我们记 \(dp_{i,0,x,y}\) 为考虑编号 \(\leq i\) 的牌,去掉 \(x\) 个编号为 \(i-1\) 和 \(x+y\) 个编号为 \(i\) 的牌后,最多可以组成的面子数量,记 \(dp_{i,1,x,y}\) 为在这些牌中选一个雀头后最多可以组成的面子数量。

我们在从 \(dp_{i}\) 转移到 \(dp_{i+1}\) 的时候,不难发现 \(i+1\) 这种牌的贡献只可能是这几种:做顺子的第一张(对应 \(y\)),做顺子的第二张(对应 \(x\)),做顺子的第三张(对应 \(dp_i\) 的 \(x\) 转移到 \(dp\) 值)和做刻子(直接转移到 \(dp\) 值)。

如果 \(dp_{i,1}\) 的某个值已经为 \(4\),或者 \(dp_i\) 对应前 \(i\) 位已经有 \(7\) 个对子,我们就认定这个状态可以是终止状态了,不再继续转移。

由于三个相同的顺子等价于三个刻子,我们发现 \(x,y<3\),因此 \(dp_i\) 只有 \(18\) 种可能。而由于某些神奇的原因,这 \(18\) 种可能只能组成大约 \(2000\) 个 \(dp_i\)!于是现在只有 \(2000\) 个本质不同的 \(dp_i\) 了,我们就可以用 \(f_{st,j,k}\) 表示状态为 \(st\),已经选了前 \(j\) 种共 \(k\) 张牌的情况数了。

时间复杂度 \(O(n^2|S|)\),\(S\) 代表 \(dp_i\) 的集合。

上一篇:【考试总结】2021-02-19 继续


下一篇:数组题目:最大连续 1 的个数