题解 P7914 【[CSP-S 2021] 括号序列】

enucai · 2021-11-01 21:57:02 · 题解

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

前言

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

看了一下现在已经有的3篇题解，都是要用两个dp数组或者要复杂地处理算重方案的，但是蒟蒻太菜，不想推这么复杂的，于是在赛后参考了@wdssean的思路，写了这一篇题解。个人觉得自己的思路还是蛮清晰的。

思路简述

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

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

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

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

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

• • 没什么好解释的
• 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)
• • 加括号时，里面可以是全*，可以是有一边是*，也可以是两边都不是*，唯独不能两边都是*且中间有括号序列。
• 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。