自动搬运

查看原文

来自洛谷，原作者为

	enucai Remake.

搬运于2025-08-24 22:34:14，当前版本为作者最后更新于2021-11-01 21:57:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一篇不需要处理算重的题解

前言

作者是一个考场上没推出来的蒟蒻

看了一下现在已经有的3篇题解，都是要用两个dp数组或者要复杂地处理算重方案的，但是蒟蒻太菜，不想推这么复杂的，于是在赛后参考了

思路简述

首先肯定是区间dp，令 $dp_{i,j}$ 表示从位置 $i$ 到位置 $j$ 一共的合法序列总情况数量。

但是不同的形态可能会有不同的转移，如：(S)这种只能从S转移过来等等。所以只开两维的dp状态必然是不够的。

直接将方法吧。将两位的dp扩充为三维，第三位表示不同的形态种类，dp状态就变成了 $dp_{i,j,[0,5]}$。没种状态表示：

• $dp_{i,j,0}$: 形态如***...*的括号序列（即全部是*）。

• $dp_{i,j,1}$: 形态如(...)的括号序列（即左右直接被括号包裹且最左边括号与最右边的括号相互匹配）。

• $dp_{i,j,2}$: 形态如(...)**(...)***的括号序列（即左边以括号序列开头，右边以*结尾）。

• $dp_{i,j,3}$: 形态如(...)***(...)*(...)的括号序列（即左边以括号序列开头，右边以括号序列结尾，注意：第2种形态也属于这种形态）。

• $dp_{i,j,4}$: 形态如***(...)**(...)的括号序列（即左边以*开头，右边以括号序列结尾）。

• $dp_{i,j,5}$: 形态如***(...)**(...)**的括号序列（即左边以*开头，右边以*结尾，注意：第1种形态也属于这种形态）。

设定完状态以后，转移就直接出来了，注意：为了防止连续超过 $k$ 个*一起出现，转移的时候不能把两段*拼接起来，在状态1的时候暴力判断一下两端的距离是否是 $\le k$ 的，是的才能转移。

作为一篇题解，转移虽然很简单，但是好得说一下吧。

• $dp_{l,r,0}$（直接特判）

• • 没什么好解释的

• $dp_{l,r,1}=(dp_{l+1,r-1,0}+dp_{l+1,r-1,2}+dp_{l+1,r-1,3}+dp_{l+1,r-1,4})*compare(l,r)$

• • $compare(i,j)$ 表示第 $i$ 位与第 $j$ 位能否配对成括号，能则为 $1$，否则为 $0$。
• • 加括号时，里面可以是全*，可以是有一边是*，也可以是两边都不是*，唯独不能两边都是*且中间有括号序列。

• $dp_{l,r,2}=\sum\limits_{i=l}^{r-1} dp_{l,i,3}\times dp_{i+1,r,0}$

• • 左边以括号序列开头且以括号序列结尾的是第3种，右边接一串*，是第0种。

• $dp_{l,r,3}=\sum\limits_{i=l}^{r-1} (dp_{l,i,2}+dp_{l,i,3})\times dp_{i+1,r,1}+dp_{l,r,1}$

• • 左边以括号序列开头，结尾随便，符合的有第2和第3种，右边接一个括号序列，是第1种。
• • 记得加上直接一个括号序列的。

• $dp_{l,r,4}=\sum\limits_{i=l}^{r-1} (dp_{l,i,4}+dp_{l,i,5})\times dp_{i+1,r,1}$

• • 左边以*开头，结尾随便，符合的有第4和第5种，右边接一个括号序列，是第1种。

• $dp_{l,r,5}=\sum\limits_{i=l}^{r-1} dp_{l,i,4}\times dp_{i+1,r,0}+dp_{l,r,0}$

• • 左边以*开头，以括号序列结尾，符合的是第4种，右边接一串*，是第0种。
• • 记得加上全是*的。

最后，答案必须以括号序列开头，以括号序列结尾，所以直接是 $dp_{1,n,3}$。

这样，初始状态也就没什么问题了，对于所有的 $i$ 满足 $1\le i \le n$，有 $dp_{i,i-1,0}=1$ 。

最终时间复杂度 $O(6\times n^3)$ 不到，（后半部分填不满 $n^3$ ）。

记得开long long，并且取模。

代码示范

Talk is cheap, show me the code.

代码挺短的，去掉文件头才28行。

#define int long long
#define mod 1000000007
int n,k,dp[510][510][6];
char s[510];
bool compare(int a,int b) {return (s[a]=='('||s[a]=='?')&&(s[b]==')'||s[b]=='?');}
signed main(){
    n=read(),k=read();
    scanf("%s",s+1);
    For(i,1,n) dp[i][i-1][0]=1;
    For(len,1,n){
        For(l,1,n-len+1){
            int r=l+len-1;
            if(len<=k) dp[l][r][0]=dp[l][r-1][0]&&(s[r]=='*'||s[r]=='?');
            if(len>=2){
                if(compare(l,r)) dp[l][r][1]=(dp[l+1][r-1][0]+dp[l+1][r-1][2]+dp[l+1][r-1][3]+dp[l+1][r-1][4])%mod;
                For(i,l,r-1){
                    dp[l][r][2]=(dp[l][r][2]+dp[l][i][3]*dp[i+1][r][0])%mod;
                    dp[l][r][3]=(dp[l][r][3]+(dp[l][i][2]+dp[l][i][3])*dp[i+1][r][1])%mod;
                    dp[l][r][4]=(dp[l][r][4]+(dp[l][i][4]+dp[l][i][5])*dp[i+1][r][1])%mod;
                    dp[l][r][5]=(dp[l][r][5]+dp[l][i][4]*dp[i+1][r][0])%mod;
                }
            }
            dp[l][r][5]=(dp[l][r][5]+dp[l][r][0])%mod;
            dp[l][r][3]=(dp[l][r][3]+dp[l][r][1])%mod;
        }
    }
    printf("%lld\n",dp[1][n][3]);
}

都看到这里了，点个赞再走呗qwq。