dp 套 dp（dp of dp）

2个月前发布

简要介绍

dp of dp 的题的形式一般是让你求满足…条件的…的数量。
直接 dp 可能不是很好用一个状态来刻画是否满足条件。
但是判定一个东西是否满足条件可以用一个比较简单的 dp 来处理。
这样我们可以用内层 dp 的结果作为外层 dp 的状态，就容易刻画出满足…条件这个限制了。

因为我不会自动机，就用普通 dp 的术语来描述了。

这么说还是很抽象，所以我们通过几道例题来进一步解析。

I. [TJOI2018] 游园会

这应该算是 dp 套 dp 板子。

下面称输入给出的奖章串为 \(s\)，要求的兑奖串为 \(t\)。

会发现题目中的 \(t\) 有三个限制：

长度为 \(N\)，且只有 N,O,I 三个字符。
与 \(s\) 的 LIS 为 \(len\)。
不能出现子串 NOI。

会发现限制 \(1\) 可以直接在 dp 转移的时候满足，限制 \(3\) 直接多加一维状态 \(0/1/2\) 表示现在的后缀和 NOI 的匹配位数即可。
即我们的 dp 状态应该是 \(dp_{i,S,0/1/2}\) 表示填到 \(t\) 的第 \(i\) 位，当前状态是 \(S\)，后缀和 NOI 的匹配位数是 \(0/1/2\) 的方案数。
但是限制 \(2\) 极其不好记录状态，因为你需要知道当前匹配到 \(s\) 的第几位，而直接记录匹配到 \(s\) 的第几位的话又容易算重。

考虑我们是怎么判定一个给定的 \(t\) 和 \(s\) 的 LIS 是否为 \(i\) 的。
显然就是先求出他们的 LIS 再判断。
这是一个经典 dp，设 \(f_{i,j}\) 表示 \(t[1,i]\) 和 \(s[1,j]\) 匹配的 LIS，转移：
\(f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+(t_i==s_j))\)。

发现我们要计算出 \(f\) 第 \(i\) 行的所有值，需要的只是 \(t_i\) 和 \(f\) 第 \(i-1\) 行的所有值。
所以最外层 dp 的状态的 \(S\) 我们直接让他表示内层 dp 的第 \(i\) 行的所有值。
外层 dp 的转移就枚举下一个位置 \(t_{i+1}\) 是什么，并对第二维 \(S\) 再做一遍 LIS 的那个 dp，得到新的状态 \(S’\)（即内层 dp \(f\) 数组的第 \(i+1\) 行）。
这样就转移成功了。

但是很明显 \(S\) 的数量太多了，时间空间双爆炸。
但显然并不是所有的 \(S\) 都是合法的。
因为 \(0\le f[i][j]-f[i][j-1]\le 1\)，所以 \(S\) 表示的序列的差分数组每一位都一定是 \(0/1\)。
因此状态 \(S\) 可以改为记录内层 dp \(f\) 数组的第 \(i\) 行的差分数组。
进一步地，可以直接状压成一个二进制数。
这样 \(S\) 的总数就是 \(2^K\) 了。

状态数是 \(O(N2^K)\)，转移在 \(O(1)\) 枚举完 \(t_{i+1}\) 之后需要对内层 dp 进行 \(O(K)\) 的转移。
复杂度 \(O(NK2^K)\)。

转移好函数的封装并不难写，实现参考了第一篇题解。
注意滚动数组并稍微剪枝。

因为在进行外层 dp 转移的时候还要对内层 dp 进行一次转移，所以叫 dp 套 dp。

code：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,mod=1e9+7;

inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
	return w*s;
}
int n,k,dp[2][(1<<15)+5][3],f1[20],f2[20],ans[20];
char s[20];
int Hash(int f[20]){   //把一个数组的差分数组状压
	int S=0;
	for(int i=0;i<k;i++) S+=(f[i+1]-f[i])*(1<<i);
	return S;
}
void decrypt(int f[20],int S){  //解压缩
	for(int i=0;i<k;i++) f[i+1]=S>>i&1;
	for(int i=1;i<=k;i++) f[i]+=f[i-1];
}
void DP(int S,int newi,int newj,char c,int val){
	decrypt(f1,S);
	for(int i=1;i<=k;i++) f2[i]=max({f2[i-1],f1[i],f1[i-1]+(c==s[i])});
	int S2=Hash(f2);
	(dp[newi&1][S2][newj]+=val)%=mod;
}
signed main(){
	n=read(),k=read();
	scanf("%s",s+1);
	
	dp[0][0][0]=1;
	for(int i=0;i<n;i++){
		for(int S=0;S<(1<<k);S++) dp[i&1^1][S][0]=dp[i&1^1][S][1]=dp[i&1^1][S][2]=0;
		for(int S=0;S<(1<<k);S++){
			if(dp[i&1][S][0]){   //这个剪枝很重要
				DP(S,i+1,1,'N',dp[i&1][S][0]);
				DP(S,i+1,0,'O',dp[i&1][S][0]);
				DP(S,i+1,0,'I',dp[i&1][S][0]);
			}
			
			if(dp[i&1][S][1]){
				DP(S,i+1,1,'N',dp[i&1][S][1]);
				DP(S,i+1,2,'O',dp[i&1][S][1]);
				DP(S,i+1,0,'I',dp[i&1][S][1]);
			}
			
			if(dp[i&1][S][2]){
				DP(S,i+1,1,'N',dp[i&1][S][2]);
				DP(S,i+1,0,'O',dp[i&1][S][2]);
			}
		}
	}
	
	for(int S=0;S<(1<<k);S++){   //显然 S 的 1 的个数就是这个内层 dp DP 出来的 LIS 的长度
		(ans[__builtin_popcount(S)]+=((dp[n&1][S][0]+dp[n&1][S][1])%mod+dp[n&1][S][2])%mod)%=mod;
	}
	for(int i=0;i<=k;i++) printf("%d\n",ans[i]);
	return 0;
}

II.开心消消乐

题面

数据范围： \(N\le 1e5，T\le 10，N 是奇数\)。

考虑如何判断一个没有 ? 的序列合不合法。

题目中的操作不好顺序处理，转换一下：
相当于把原序列分成 \(\lfloor \frac{n}{2} \rfloor\) 个块 \([1,2],[3,4],[5,6],…,[n-2,n-1]\) 和最后一个数。
并维护一个栈，栈里面存储的是块。
我们一次考虑每个块，如果当前考虑的块是 \((x,y)\)，那相当于有两种操作：

把 \(x\) 和栈中所有块依次合并，直到栈中只剩一个数 \(z\)，将 \((z,y)\) 放入栈。
直接把 \((x,y)\) 丢入栈。

考虑完所有块后让最后一个数和栈中的块依次合并，最后得到的数就是结果。
判断就是要判断是否存在一种操作方式使得最后可以得到 \(1\)。
你会发现，我们其实不在乎这个栈具体长什么样，只在乎当我们把一个数 \(x\) 和栈中的所有块合并完之后会得到什么数。
即我们只需要维护栈所对应的函数 \(f:x\to (a,b)\) 表示当 \(x=0\) 时，会得到 \(a\)，当 \(x=1\) 时会得到 \(b\)。
并且对于这两种操作都可以快速更新出新的 \(f\)。

于是我们考虑 dp 设 \(dp_{i,a,b}\) 表示是否可以在考虑完第 \(i\) 个块之后得到函数 \(f:x->(a,b)\)。
转移显然，于是我们完成了判定。

对于计数，因为这个判定的 dp 的后两维只有 \(4\) 种情况，且 dp 值天然地只有 \(0/1\) 两种情况。
所以直接上 dp of dp 即可。
状态数是 \(O(2^4 \times n)\)。

code

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second 
using namespace std;
const int N=1e5+5,mod=998244353;

inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
	return w*s;
}
int T,n;
char c[10],s[N];
int calc(char x,char y,char z){
	int u=x-'0',v=y-'0',w=z-'0';
	return c[(w<<2)+(v<<1)+u]-'0';
}
int dp[N][(1<<4)+5];
bool f1[2][2],f2[2][2];
int Hash(bool f[2][2]){
	return (f[0][0]<<3)+(f[0][1]<<2)+(f[1][0]<<1)+f[1][1];
}
void decrypt(bool f[2][2],int S){
	f[0][0]=S>>3&1;
	f[0][1]=S>>2&1;
	f[1][0]=S>>1&1;
	f[1][1]=S&1;
}
void DP(int newi,int S,char x,char y,int val){
	decrypt(f1,S);
	f2[0][0]=f2[0][1]=f2[1][0]=f2[1][1]=false;
	for(int a=0;a<=1;a++){
		for(int b=0;b<=1;b++){
			//转移 1：先放 x，再放 y
			if(x=='0') f2[calc(a+'0',y,'0')][calc(a+'0',y,'1')]|=f1[a][b];
			else f2[calc(b+'0',y,'0')][calc(b+'0',y,'1')]|=f1[a][b];
			
			//转移 2：把 (x,y) 直接丢进栈里
			int a1=calc(x,y,'0'),b1=calc(x,y,'1');
			if(a1==0&&b1==0) f2[a][a]|=f1[a][b];
			else if(a1==0&&b1==1) f2[a][b]|=f1[a][b];
			else if(a1==1&&b1==0) f2[b][a]|=f1[a][b];
			else f2[b][b]|=f1[a][b];
		}
	}
	int S2=Hash(f2);
	(dp[newi][S2]+=val)%=mod;
}
void work(){
	memset(dp,0,sizeof dp);
	dp[0][4]=1;
	for(int i=1;i<n;i+=2){
		int id=(i+1)/2;
		for(int S=0;S<(1<<4);S++){
			if(s[i]=='?'&&s[i+1]=='?'){
				DP(id,S,'0','0',dp[id-1][S]);			
				DP(id,S,'0','1',dp[id-1][S]);			
				DP(id,S,'1','0',dp[id-1][S]);			
				DP(id,S,'1','1',dp[id-1][S]);			
			}
			else if(s[i]=='?'){
				DP(id,S,'0',s[i+1],dp[id-1][S]);
				DP(id,S,'1',s[i+1],dp[id-1][S]);
			}
			else if(s[i+1]=='?'){
				DP(id,S,s[i],'0',dp[id-1][S]);
				DP(id,S,s[i],'1',dp[id-1][S]);
			}
			else DP(id,S,s[i],s[i+1],dp[id-1][S]);
		}
	}
	int id=(n-1)/2,ans=0;
	for(int S=0;S<(1<<4);S++){
		decrypt(f1,S);
		if(s[n]!='1') if(f1[1][0]||f1[1][1]) (ans+=dp[id][S])%=mod;
		if(s[n]!='0') if(f1[0][1]||f1[1][1]) (ans+=dp[id][S])%=mod;
	}
	printf("%d\n",ans);
}
signed main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s%s",c,s+1);
		n=strlen(s+1);
		work();
	}
	return 0;
}

来源链接：https://www.cnblogs.com/FloatingLife/p/18739432

评分

欢迎为Ta评分