(2022杭电多校四)1001-Link with Bracket Sequence II（区间动态规划）

题目链接：杭电多校4 - Virtual Judge

题目：

 样例输入：

3
4 2
1 0 0 -1
4 2
0 0 0 -1
6 3
0 0 0 0 0 0

样例输出：

3
4
135

题意：多组数据，对于每一组数据，先给出一个n和m，n代表括号序列，m代表括号总数。接下来给出n个数，第i个数ai可能是一个正数x，代表第i个位置是第x种括号的左括号，如果ai是一个负数x，那么代表第i个位置是第|x|种括号的右括号，如果ai是0，那么就代表当前位置为空，就是可以填入任意一种括号。最后问我们合法的序列种数是多少？答案对1e9+7取模。

分析：这是一道括号匹配的区间动态规划题目。

设f[i][j]表示区间[l,r]相匹配的方案数，g[i][j]表示区间[l,r]相匹配且第l个括号和第j个括号相匹配的方案数。

我们枚举区间[l,r]，先来考虑g[i][j]怎么更新，根据其定义我们可以知道，g[i][j]=e*f[i+1][j-1]，其中e代表第l个括号和第r个括号匹配的方案数，下面我们来看一下e的可能情况。

首先要保证第l个位置是左括号，第r个位置是右括号，也就是说a[l]>=0&&a[r]<=0

(1)a[l]=a[r]=0 这种情况就是说，第l个括号和第r个括号都是任取的，由于总共有m种括号，所以此时e=m

(2)a[l]+a[r]=0这种情况就是说，第l个括号和第r个括号都已经固定且恰好匹配，那么只有一种方案，即e=1

(3)a[l]和a[r]种只有一个为0，那么另一个括号原则上可以任取，但是由于一个括号已经固定，为了使两者进行匹配，所以另一种括号也只有取一种括号形式，即e=1

对于其他的方案都无法使得第l个括号和第r个括号序列进行匹配，即e=0

现在我们已经知道g数组如何更新了，下面我来分析一下如何更新f数组：

这就是经典的区间动态规划的方法，枚举中间点k，下面是更新代码：

两种更新方法均可，区别就是边界不同
for(int k=l;k<=r;k++)
	f[l][r]=(f[l][r]+f[l][k-1]*g[k][r])%mod;//注意f数组和g数组的区别 
for(int k=l;k<=r;k++)
	f[l][r]=(f[l][r]+g[l][k]*f[k+1][r])%mod;//注意f数组和g数组的区别

这里要注意的一点是，动态方程里面是f[l][k-1]*g[k][r]，不能是f[l][k-1]*f[k][r]，原因就在于对于（）（）（）这种的方案我们在f[1][2]*f[3][6]时会计算一次，在枚举f[1][4]*f[5][6]时又会枚举一次就会造成重复。更不能是g[l][k-1]*g[k][r]，原因在于我们这样更新只能更新（…合法序列…）（…合法序列…）这样的括号序列，如果有（…合法序列…）（…合法序列…）（…合法序列…）的括号序列那么我们利用这种方式就更新不到。而g[l][k]*f[k+1][r]更新为什么就是对的呢？其实原因很简单，就是对于任意一种括号序列都可以表示成（……）……的形式，其中右边……的形式不唯一，也不要求最左边和最右边括号必须匹配，只要求整体是匹配的就行。而且这种分配方式是唯一的，这是显然的，因为我们从左边取出了两端恰好匹配的一个括号序列，这个括号序列是唯一的，所以这样就会不重不漏地记录答案。同理f[l][k-1]*g[k][r]的证明与上面是一样的，只不过是把括号序列表示成……（……）的形式而已，这里就不赘述了。

下面是代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=503+10,mod=1e9+7;
typedef long long ll;
ll f[N][N];//f[i][j]表示区间[l,r]相匹配的方案数
ll g[N][N];//g[i][j]表示区间[l,r]相匹配且第l个括号和第j个括号相匹配的方案数
int a[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			f[i][j]=g[i][j]=0;
		for(int i=0;i<=n;i++)  f[i+1][i]=g[i+1][i]=1;
		for(int len=2;len<=n;len++) 
		for(int l=1;l+len-1<=n;l++)
		{
			int r=l+len-1;
			ll e;//第l个位置和第r个位置匹配的括号种数 
			if(a[l]>=0&&a[r]<=0)//保证第l个位置可以是左括号第r个位置可以是右括号 
			{
				if(a[l]==0&&a[r]==0)//括号可以任取
					e=m;
				else if(a[l]+a[r]==0)//括号已经匹配 
					e=1;
				else if(a[l]==0||a[r]==0)//一个括号类型已经固定那么另一个括号也只有一种选择 
					e=1;
				else//两个括号都已经固定但是无法匹配 
					e=0;
				g[l][r]=e*f[l+1][r-1]%mod;//固定了两端，内部括号随机 
			}
			//两种更新方法均可 
//			for(int k=l;k<=r;k++)
//				f[l][r]=(f[l][r]+f[l][k-1]*g[k][r])%mod;//注意f数组和g数组的区别 
			for(int k=l;k<=r;k++)
				f[l][r]=(f[l][r]+g[l][k]*f[k+1][r])%mod;//注意f数组和g数组的区别
		}
		printf("%lld\n",f[1][n]);
	}
	return 0; 
}