dp套dp

文章dp套dp分享给大家，欢迎收藏极客之家，专注分享技术知识

我们先说一下 \(dp\) 套 \(dp\) 大概是个什么东西。

感性理解一些，你现在有一个动态规划数组 \(g\)，然后你的 \(f\) 用 \(g\) 的某种方式作为下标进行转移。

事实上，这个 \(g\) 需要满足单调性，然后相当于你是在一个 \(DAG\) 上做 \(dp\)。为什么要满足单调性，否则有可能出现环，有环代表你的状态有后效性，有后效性则无法转移。

游园会

首先最长公共子序列的动态规划是好做的，这里就不说了。

这里设最长公共子序列的动态规划数组为 \(g\)。

我们先设 \(f_{i,{w_1,w_2,\cdots,w_k}}\) 为 长度为 \(i\) 且 \(g_{i,j}=w_j\) 的字符串个数。

但是你发现 \(w\) 你存不下来。于是我们考虑有没有什么性质能够版主我们优化。

显然有 \(g_{i,j}-g_{i,j-1}\le 1\)。于是你考虑 \(f\) 的后面维度不存储真正意义上的 \(w\)，而存储 \(w\) 的差分数组，于是每一位都是 \(0\) 或者 \(1\)。状态数共 \(n\times 2^k\)，可以接受。

但是你又发现，我们知道 \(s_i\)（题目给出），也就是说当前的 \(g_i\) 只跟 \(t_i\) 和 \(g_{i-1}\) 有关。于是我们在做 \(g\) 的转移时只记 \(g_{i-1}\) 就行（就是滚动数组优化）。

然后是我们的 \(f\) 也可以用滚动数组优化，否则空间会爆。

代码：

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define N 40005
using namespace std;
int n,k,f[2][N][3],g[2][20],cnt[N],res[20];
char s[20];
void solve1(int state){
	memset(g[0],0,sizeof g[0]);
	for(int i=0;i<k;i++){
		g[0][i+1]=state>>i&1;
	}
	for(int i=1;i<=k;i++){
		g[0][i]+=g[0][i-1];
	}
}
int solve2(){
	int state=0;
	for(int i=1;i<=k;i++){
		int x=g[1][i]-g[1][i-1];
		state|=x*(1<<i-1);
	}
	return state;
}
void solve(int cur,int state,char c,int now,int las){
	if(las==0)return;//没有贡献不用转移 
	if(c=='I'&&now==2)return;//包含了子串NOI 
	int ne=c=='N'?1:0;//如果是N，下一个就从I匹配，否则从N 
	if(now==0&&c=='N')ne=1;//如果当前应匹配第0个且是N，后跳一位 
	else if(now==1&&c=='O')ne=2;//同上 
	solve1(state);//把差分记录的状态还原 
	memset(g[1],0,sizeof g[1]);//先清空 
	for(int i=1;i<=k;i++){
		if(s[i]==c){//如果s_i=t_j，可以使用特殊转移 
			g[1][i]=max(g[1][i],g[0][i-1]+1);//这里的g_{0,i-1}就是lcs_{i-1,j-1} 
		}
		g[1][i]=max({g[1][i],g[0][i],g[1][i-1]});//否则使用一般转移（g_{0,i}就是lcs_{i,j-1}，g_{1,i-1}就是lcs_{i-1,j} 
	}
	int res=solve2();//再把当前数组弄成差分状态存进去 
	(f[cur][res][ne]+=las)%=mod;//继承上一个 
} 
signed main(){
	cin>>n>>k>>s+1;
	int cur=0;
	f[0][0][0]=1;
	for(int i=1;i<=n;i++){
		cur^=1;
		memset(f[cur],0,sizeof f[cur]);
		for(int j=0;j<1<<k;j++){
			for(int p=0;p<3;p++){
				char c=p==0?'N':p==1?'O':'I';
				solve(cur,j,c,0,f[cur^1][j][0]);
				solve(cur,j,c,1,f[cur^1][j][1]);
				solve(cur,j,c,2,f[cur^1][j][2]);
			}
		}
	}
	for(int i=1;i<1<<k;i++){
		cnt[i]=cnt[i>>1]+(i&1);//cnt是这个数二进制表示有几个1，这里有几个1代表lcs长度就是几 
	}
	for(int i=0;i<1<<k;i++){
		for(int j=0;j<3;j++){
			(res[cnt[i]]+=f[cur][i][j])%=mod;
		}
	}
	for(int i=0;i<=k;i++){
		cout<<res[i]<<'\n';
	}
	return 0;
}

小 N 的独立集

独立集是指，一堆点他们两两之间没有边。最大权独立集是指，所有的独立集中，权值之和最大的那个。

这道题我们从部分分说起。

• \(n\le 8\)

枚举所有可能的权值分配。然后参照这道题写个动态规划就行了。

• \(n\le 100\)

首先 \(f\) 数组与这道题的设立相同。

我们考虑将 \(f\) 数组的值设为状态。

设 \(g_{u,v_0,v_1}\) 为 \(f_{u,0}=v_0,f_{u,1}=v_1\) 的方案数。

我们枚举 \(i,j,p,q\) 分别为 \(f_{u,0},f_{u,1},f_{v,0},f_{v,1}\)。

于是有 \(g'_{u,i+\max(p,q),j+p}\rightarrow g'_{u,i+\max(p,q),j+p}+g_{u,i,j}\times g_{v,p,q}\)。

• \(n\le 1000\)

上述转移无法通过的一个重要原因是，我们的状态复杂度过高，所以我们要优化状态。

我们重新定义 \(f_{u,1/0}\) 为 \(u\) 子树内是否强制不选节点 \(u\) 时的最大权值。于是有 \(0\le f_{u,0}-f_{u,1}\le k\)。因为两者之差不超过 \(u\) 点的权值，而权值不超过 \(k\)，这样就优化掉了一个 \(n\)。

于是 \(g_{u,v_1,d}\) 为 \(u\) 子树内 \(f_{u,0/1}\) 分别为 \(v_1+d,v_1\) 的方案数，然后还是枚举 \(i,j,p,q\)，有：\(g'_{u,i+p+q,\max(i+j+p,i+p+q)-(i+p+q))}\rightarrow g'_{u,i+p+q,\max(i+j+p,i+p+q)-(i+p+q))}+g_{u,i,j}+\times g_{v,p,q}\)。

此时复杂度 \(O(n^2\times k^4)\)，可以通过。

版权声明：本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！