自动搬运

查看原文

来自洛谷，原作者为

	DengDuck 澳門現役 OIer，萌萌未花日奈雙推人一枚

搬运于2025-08-24 21:44:51，当前版本为作者最后更新于2023-07-28 14:31:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不知道为啥我的代码格外短。

首先根据题目给出的定义，我们可以考虑进行一个转化，把左括号看成 $1$，右括号看成 $-1$，这样合法括号序列可以看成任意前缀和非负，区间和为 $0$ 的序列。

我们由此可以列出一个 $\mathcal O(n^3)$ 的动态规划方案：

$f_{i,j,k}$ 表示染色到第 $i$ 项，黑色前缀和为 $j$，白色前缀和为 $k$ 的方案。

转移如下：

边界条件为 $f_{0,0}=1$。

$A_i$ 表示经过转换之后我们的数组的第 $i$ 项。

其实有用的状态并不多，剪剪枝卡卡空间可以过。

但是这个时间复杂度不够优秀，我们考虑进一步化简。

我们发现对于一个 $i$ 而言，有用的 $j+k$ 是不变的，为数组 $A$ 的前 $i$ 项的前缀和，这点观察式子也可以发现。

所以我们只维护 $j$ 一维，保证 $k$ 不为负数即可。

$k$ 非负如何保证？我们发现 $k=sum-j$，其中 $sum$ 是当前前 $i$ 项的前缀和，我们只要保证 $j\leq sum$ 即可。

时间复杂度降为 $O(n^2)$。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=2e3+5;
const LL mod=2012;
LL n,f[N][N],sum,a[N];
char s[N];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='(')a[i]=1;
		else a[i]=-1;
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		for(int j=0;j<=sum;j++)
		{
			f[i][j]=f[i-1][j];
			if(0<=j-a[i])f[i][j]+=f[i-1][j-a[i]];
			f[i][j]%=mod;
		}
	}
	printf("%lld",f[n][0]);
}