[CSP-S模拟测试]:计数（DP+记忆化搜索）

题目描述

既然是萌萌哒$visit\text{_}world$的比赛，那必然会有一道计数题啦！
考虑一个$N$个节点的二叉树，它的节点被标上了$1\sim N$的编号。并且，编号为$i$的节点在二叉树的前序遍历中恰好是第$i$个出现。
我们定义$A_i$表示编号为$i$的点在二叉树的中序遍历中出现的位置。
现在，给出$M$个限制条件，第$i$个限制条件给出了$u_i,v_i$，表示$A_{u_i},A_{v_i}$你需要计算有多少种不同的带标号二叉树满足上述全部限制条件，答案对$10^9+7$取模。

输入格式

第一行一个整数$T(1\leqslant T\leqslant 5)$，表示数据组数。
每组数据第一行为两个整数$N,M$，意义如题目所述。
接下来$M$行，每行两个整数$u_i,v_i(1\leqslant u_i,v_i\leqslant N)$。描述一条限制。

输出格式

对每组数据，输出一行一个整数，表示答案。

样例

样例输入：

3
5 0
3 2
1 2
2 3
3 3
1 2
2 3
3 1

样例输出：

42
1
0

数据范围与提示

样例解释：

第一组数据，无任何限制时，$5$个点的二叉树形态个数为$42$。
第二组数据，唯一满足条件的二叉树的形态为$1-2-3$。（$1$为根，$2,3$均为右儿子）。
第三组数据，限制条件产生矛盾。

数据范围：

对于全部的测试数据，保证$T\leqslant 5,N\leqslant 400,M\leqslant 10^3$
子任务$1$（$20$分）：$M=0$。
子任务$2$（$15$分）：$N\leqslant 10$。
子任务$3$（$20$分）：$N\leqslant 50,M\leqslant 1$。
子任务$4$（$15$分）：$N\leqslant 50$。
子任务$5$（$30$分）：无特殊限制。

题解

先来复习一下三种遍历序：

　　$\alpha.$前（先）序遍历：根$\rightarrow$左$\rightarrow$右。

　　$\beta,$中序遍历：左$\rightarrow$中$\rightarrow$右。

　　$\gamma.$后序遍历：左$\rightarrow$右$\rightarrow$根。

为方便记忆，我们可以只记“根”在其中的位置就好了，先序遍历根在前，中序遍历根在中，后序遍历根在后，左在前右在后。

不妨从$M=0$的情况入手，你可能找规律发现是卡特兰数，简单证明一下：

　　可以把放到左儿子认为是$+1$，放到右儿子认为是$-1$，所以是卡特兰数。

但是如果接着往下思考它就死了……

考虑换一个思路解决这个问题，考虑$DP$，设$dp[l][r]$表示点的编号区间$[l,r]$所能组成的不同形态的数的个数。

因为需要满足前序遍历序就是点的编号，所以$l$一定是根节点，且左右子树里点的编号也是分别连续的，所以我们可以得到转移方程：

$$dp[l][r]=\sum \limits_{i=l}^r dp[l+1][i]\times dp[i+1][r]$$

接着考虑带限制的情况，其实也很简单；不妨设两点$u$和$v$，且$u$的编号比$v$小。

如果存在限制要求在中序遍历中$v$在$u$之前，那么$v$一定要在$u$的左子树中；反之同理。

于是我们可以预处理出来一定在左子树中的编号最大的点（设为$L[i]$）和一定在右子树中的编号最小的点（设为$R[i]$），那么我们可以得到：

$$dp[l][r]=\sum \limits_{i=L[l]}^{R[l]}dp[l+1][i]\times dp[i+1][r])$$

于是这道题就解决了。

时间复杂度：$\Theta(n^3)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

const int mod=1000000007;

int N,M;

bool Map[401][401];

int L[401],R[401];

long long dp[401][401];

void pre_work()

{

	memset(Map,0,sizeof(Map));

	memset(dp,-1,sizeof(dp));

}

long long dfs(int l,int r)

{

	if(l>r)return 1;

	if(L[l]>r)return 0;

	if(l==r)return 1;

	if(dp[l][r]!=-1)return dp[l][r];

	dp[l][r]=0;

	for(int i=L[l];i<=min(R[l],r);i++)

		dp[l][r]=(dp[l][r]+dfs(l+1,i)*dfs(i+1,r)%mod)%mod;

	return dp[l][r];

}

int main()

{

	int T;scanf("%d",&T);

	while(T--)

	{

		pre_work();

		scanf("%d%d",&N,&M);

		for(int i=1;i<=M;i++)

		{

			int u,v;scanf("%d%d",&u,&v);

			Map[u][v]=1;

		}

		for(int i=1;i<=N;i++)

		{

			L[i]=R[i]=i;

			for(int j=i+1;j<=N;j++)if(Map[j][i])L[i]=j;

			for(int j=i+1;j<=N;j++){if(Map[i][j])break;R[i]=j;}

		}

		printf("%lld\n",max(0LL,dfs(1,N)));

	}

	return 0;

}

rp++

巴特西