[TJOI2018] 游园会题解

[TJOI2018] 游园会(dp套dp)

• [TJOI2018] 游园会(dp套dp)
  • 前言：
  • 题目简化：
  • 解题思路：
    • 较为简单的一步：
    • 较为困难的步骤
  • 思路总结
  • 代码呈现：
  • 注释/后记：

前言：

这是和 dp 套 dp 的初遇，这不得好好了解一下。

题目简化：

先把题目进行简化，就是要构造字符串，对于 $len \in [0,k]$ 满足以下条件：

1. 只包含 $N,O,I$ 且长度为 $n$。
2. 最长公共子序列长度为 $len$。（下文都以 $S_1$ 来表示已知的这个字符串）
3. 不能存在的 $NOI$ 子串。

解题思路：

较为简单的一步：

本题的难度上在了第二点。

那我就先不管他。假如说某位神犇给你做出了一个自动机，它可以识别所有与 $S_1$ 的最长公共子序列长度恰好为 $i$ 的串。那么我们怎么统计出答案呢？

这个问题可以转化为在这个自动机上走动 $n$ 步最终走到某个状态接受点的方案数。
两个方案不同当且仅当存在一个位置 $pos$ 满足 $P1_{pos}$ 不等于 $P2_{pos}$，其中 $P_i$ 表示第 $i$ 步走的点。

这个显然是可以用动态规划解决，我们设计状态 $f_{i,j,k}$ 表示在自动机这个图上走了 $i$ 步（也可以看成目前生成的字符串长度），到达了 $j$ 这个自动机上的点，目前匹配到了 $NOI$ 中的第 $k$ 位情况下能够生成的字符串的方案数。
假设我们现在在自动机的节点 $j$ 上完成了这一次转移，而且根据神犇的自动机知晓了到达这个点时的最长公共子序列为 $p$ ，那么他会对最终 $ans_p$ 产生这个 dp 值的贡献。

这个dp柿子的话很简单，就不再赘述了。如此一来我们完成了自动机外的dp。

较为困难的步骤

然而世事无常，我们并没有那么多神犇愿意帮助我们蒟蒻来做这个自动机。所以接下来我们必须要面对这个问题。

我们还是要用 dp 的思想来解决建立的问题。

相信您看了其他神犇的题解后，肯定已经知道了对于任意两个字符串如何用 dp 来求解他们的最长公共子序列了吧。那么让我把这个dp柿子从上面的神犇的题解中摘抄下来。

注意一下下面这个柿子和“简单步骤”中的柿子没有任何关系。

$f(i,j)=max(f(i-1,j),f(i,j-1),f(i-1,j-1)+[a[i]==b[j]])$

注释：你一定要深刻理解这个柿子的含义再进行下一句话的阅读。
我们先假设就是在做LCS，我们的转移是两个循环，在枚举了一个字符串一位后遍历另外一个字符串求解。换句话说，我们在做普通的这道题时，通过枚举这一次选了什么字符然后遍历另一个字符串得出本次的答案。

由于其中一个字符串我们是已经知道的，不如假设 $b$ 是已知的吧。上文可知，我们完全可以通过知道这一次 $a$ 选的什么字符，然后遍历 $b$ 来搞。我们看看缺了哪些条件？显然就是 $f(i-1,?)$ 这个数组以及 $a_i$。

我们把这个柿子稍微抽象话一点，将所有可能的 $f(i-1,?)$ 作为一个在自动机上的节点，通过枚举所有可能新加入的字符，在自动机进行一波转移。

然后呢，很显然的是，我肯定会炸空间，因为状态数量太多了。这里有两种解决方法，都是需要发现一定的性质。

1. 可以发现这个 $f$ 是单调不减的，那么我们做一个差分，就是长度为15的01数组，显然可以状态压缩。最后的时候大不了再前缀和。
2. 可以发现很多方案其实在里面是不合法的、无用的。那么我们可以利用哈希来做（这就是第一篇题解的做法）。

我选择的是第一种做法，毕竟不管在什么时候二进制都是比较吃香的。
那么接下来，只需要把“简单步骤”中的 $j$ 给替换成状压就好了。

思路总结

接下来总结一下我们的做此题的思路。

1. 首先进行输入和将 $N，O，I$ 映射成数。

2. 然后现在进行 dp ,具体地，现在第一层层枚举走的步数 $i$，第二层枚举我们的差分出的二进制状态，接着再枚举三种状态，在这三层中对三种情况进行dp，为保持好看，我们可以专门写一个函数。包括下文将要提到的“压缩”和“解压”也可以用一个函数保持美观。

3. 在这个函数中，我们首先将绝对不合法的情况舍去（直接返回），然后根据现在枚举的将填入的字符以及上一次填入字符（可以根据dp得到）来判断这一次结束后的第三维的状态应该是什么（这里暂时记为 $nxt$）。接着我们将已经知道的当前差分的状态“解压”达成正常状态。接着跑一遍 LCS 的一层循环，跑完后可以得到更新后的数组，我们又将它差分压缩，得到更新的状态。最后在最新的状态以及 $nxt$下加上上一次转移过来的答案。

4. 在我们得到了 dp 值后，考虑怎么统计答案……对于所有的状态，我们只需要找到他“解压”后的值，得到他的 LCS，然后开个桶直接装下 dp 值就好了。

代码呈现：

#include<bits/stdc++.h>
using namespace std;
map<char,int>mp;
const int mod=1e9+7;
int n,k;
int maxn,op;
int f[2][1<<15][3];
int presum[20];
int newpre[20];
int ans[20];
int cnt[1<<15];
string s;
void init(){
	mp['N']=0;mp['O']=1;mp['I']=2;
	maxn=1<<k;
	op=0;
	f[op][0][0]=1;
}
void getpre(int S){//将S这个差分状态的01序列打开，利用前缀和搞定 
	for(int i=0;i<k;i++){
		presum[i+1]=(S>>i&1);
	}
	for(int i=1;i<=k;i++){
		presum[i]=presum[i-1]+presum[i];
	}
}
int getdis(){//将得到的新的前缀数组差分压缩 
	int ret=0;
	for(int i=1;i<=k;i++){
		ret|=((newpre[i]-newpre[i-1])<<(i-1));
	}
	return ret;
}
void change(int cur,int S,int nowc,int prec,int preans){
	if(preans==0||(prec==2&&nowc==2)){//如果前面的都没有的答案|现在的答案不合法 
		return; 
	}
	int nxt=0;
	if(nowc==0){
		nxt=1;
	}
	if(prec==0&&nowc==0){
		nxt=1;
	}
	else if(prec==1&&nowc==1){
		nxt=2;
	}
	getpre(S);
	memset(newpre, 0, sizeof(newpre));
	for(int i = 1; i <= k; i++) {
		if(mp[s[i]] == nowc) {
			newpre[i] = max(newpre[i], presum[i - 1] + 1);
		}
		newpre[i] = max(newpre[i], max(presum[i], newpre[i - 1]));
	}
	int newS = getdis();
	f[cur][newS][nxt] = (f[cur][newS][nxt] + preans) % mod;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k;
	cin >> s;
	s=" "+s;
	init();
	for(int i=1;i<=n;i++){
		op=op^1;
		memset(f[op],0,sizeof(f[op]));
		for(int j=0;j<maxn;j++){
			for(int p=0;p<=2;p++){
				change(op,j,p,0,f[op^1][j][0]);
				change(op,j,p,1,f[op^1][j][1]);
				change(op,j,p,2,f[op^1][j][2]);
			}
		}
	}
	cnt[0]=0;
	for(int i=1;i<maxn;i++){
		cnt[i]=cnt[i>>1]+(i&1);
	}
	for(int i=0;i<maxn;i++) {
		for(int p=0;p<3;p++) {
			ans[cnt[i]]=(ans[cnt[i]]+f[op][i][p])%mod;
		}
	}
	for(int i=0;i<=k;i++){
		cout<<ans[i]<<endl;
	}
	
	
}

注释/后记：

在本机上跑了14秒（第4个点），但是吸氧后飞快欸！