[P7914] [CSP-S 2021] 括号序列

BMTXLRC · 2022-07-21 21:45:23 · 题解

~~不要试着拿这道题的暴力分。~~

状态的设置

看了题面，我们发现有三个变量：长度，左端点，星号个数，那我们先不妨开三维的 DP 数组 dp_{i,j,k}，表示填满区间 [i,j]，这里面有 k 个星号的方案数。经过一番推导，我们能得出两个结论：

时间复杂度高达 \mathcal{O}(n^6)。
完全没必要加上第三维。

那我们想办法消掉第三维，用 dp_{i,j} 表示填满区间 [i,j] 的方案数，我们暂且认为这是正确的，并进行接下来的推导。

状态转移方程初版

挨个情况的考虑，这里设 \text{condition}_{l,r} 表示区间 [l,r] 是否全部为星号，如果是则返回 1，否则返回 0。

设当前区间为 [l,r]，那么我们要满足的条件是 s_l=\tt ? 或者 s_l=\tt (，s_r=\tt ? 或者 s_r=\texttt {)}，其边界条件是 r-l\geqslant 2，同时中间一段必须全部为星号或问号。则状态转移方程是：

dp_{l,r}=\text{condition}_{l+1,r-1}

dp_{l,r}=dp_{l+1,r-1}

dp_{l,r}=dp_{p+1,r-1}\times\text{condition}_{l+1,p}

dp_{l,r}=dp_{l+1,p}\times\text{condition}_{p+1,r-1}

dp_{l,r}=dp_{l,p}\times dp_{p+1,r}

dp_{l,r}=dp_{l,p}\times dp_{q+1,r}\times \text{condition}_{p+1,q}

写完这些我们有两个问题：

我们的算法真的正确吗？
如何求出 \text{condition}？

对于第一个问题，样例 2 会告诉我们并不正确，比如 \texttt{()?()?()} 这样的序列，答案是 2 种，但是我们却错误的算出了 3 种，因为我们反复的算了 2 遍 \texttt{()*()*()} 这个答案，这也是我们接下来的任务：去重。

对于第二个问题，我们可以定义前缀和，求和的是 s_i 是否为两种括号中的任意一种，这样一段区间只有星号和问号，也就意味着这段区间起点和终点的前缀和值相等，这可以在 \mathcal{O}(n) 的预处理内解决。总时间复杂度已经降到了 \mathcal{O}(n^4)。

去重

为什么我们会重复的算一个答案，原因是有很多答案可以通过多种方式组合起来，比如 \texttt{(**)*()()} 这种答案，既可以通过 \texttt{(**)} 和 \texttt{()()} 采取 \texttt{ASB} 变换所得，也可以通过 \texttt{(**)*()} 和 \texttt{()} 通过 \texttt{AB} 变换所得。也就是其实去重的关键在于正确处理 \texttt{ASB} 和 \texttt{AB} 上面。

我们不妨改一下我们原本的定义，经过一番思考，我们可以发现存在多解是由于 \texttt{AB} 括号序列的可分割性方面，但是以 \texttt{(} 开头，以 \texttt{)} 结尾的所有串，都是不可分割的，这便与我们要去重的串产生了许多不同。设 dp_{l,r,0/1} 表示区间 [l,r] 的合法括号序列答案，但是 0 代表左括号开头右括号结尾的所有合法括号序列，而 1 则不是。通过这个我们可以重新思考上面的六种情况。

dp_{l,r,0}=\text{condition}_{l+1,r-1}

dp_{l,r,0}=dp_{l+1,r-1,0}+dp_{l+1,r-1,1}

dp_{l,r,0}=(dp_{p+1,r-1,0}+dp_{p+1,r-1,1})\times\text{condition}_{l+1,p}

dp_{l,r,0}=(dp_{l+1,p,0}+dp_{l+1,p,1})\times \text{condition}_{p+1,r-1}

dp_{l,r,1}=dp_{l,p,0}\times(dp_{p+1,r,0}+dp_{p+1,r,1})

dp_{l,r,1}=dp_{l,p,0}\times(dp_{q+1,r,0}+dp_{q+1,r,1})\times\text{condition}_{p+1,q}

至此我们的去重工作就完成了，但是我们的时间复杂度仍然是 \mathcal{O}(n^4) 的，其算法瓶颈在于计算 \texttt{ASB} 情况时我们必须枚举两个断点，使得算法的复杂度很高，我们必须想办法消掉一个断点。

算法优化

我们仔细观察 \texttt{ASB} 这种串，它本质上是由 \texttt{A} 和 \texttt{SA} 串结合起来的，而 \texttt{SA} 串的计算上面已经讨论过了，我们就可以只枚举断点 p，达到我们的目的。为了方便我们对 DP 数组多开一个数字 2，它用来表示区间 [l,r] 组成 \texttt{SA} 串的总方案数，而他的转移是 \mathcal{O}(n^3)，调用答案时间却达到了 \mathcal{O}(1)，成功的消掉了多余的复杂度。

如果你是 TLE 95 分，检查一下你是不是取模取多了，减少取模的式子可以有效减少时间。

细节

计算 \texttt{(SA)} 的情况时，一定要注意 p 的上界，看看你是否因为这个而 RE。

对于所有的情况都要想清楚 r 至少要在 l 的多少位后，手推一下样例也是完全可行的。

最终输出一定要取模。

初始化是对于所有的问号和括号，看他下一位是否可能匹配，并进行初始化，单独的星号是没法成为合法括号序列的，不用管它。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=5e2+5;
int n,k,dp[N][N][3],d[N];
char s[N];
signed main(){
    scanf("%lld %lld",&n,&k);
    scanf("%s",s+1);
    for(register int i=1;i<=n;i++){
        d[i]=d[i-1];
        if((s[i]=='('||s[i]=='?')&&(s[i+1]==')'||s[i+1]=='?')) dp[i][i+1][0]=1;
        if(s[i]=='('||s[i]==')') d[i]=d[i-1]+1;
    }
    for(register int i=2;i<=n;i++){
        for(register int l=1;l<=n;l++){
            int r=l+i-1;
            if(r>n) break;
            if(r-l>=2&&(s[l]=='('||s[l]=='?')&&(s[r]==')'||s[r]=='?')){
                dp[l][r][0]=((dp[l][r][0]+dp[l+1][r-1][1])%mod+dp[l+1][r-1][0])%mod;//情况(A)
            }
            if(r-l>=2&&((d[r-1]-d[l])==0)&&(s[l]=='('||s[l]=='?')&&(s[r]==')'||s[r]=='?')&&r-l-1<=k){//情况(S)
                dp[l][r][0]=(dp[l][r][0]+((d[r-1]-d[l])==0))%mod;
            }
            if(r-l>=3){
                for(register int p=l;p<r;p++){
                    dp[l][r][1]=((dp[l][p][0]%mod*(dp[p+1][r][0]+dp[p+1][r][1])%mod)%mod+dp[l][r][1])%mod;//情况AB
                }
            }
            if(r-l>=4&&(s[l]=='('||s[l]=='?')&&(s[r]==')'||s[r]=='?')){
                for(register int p=r-k-1;p<r-1;p++){//情况(AS)
                    if(r-p-1<=k) dp[l][r][0]=(dp[l][r][0]+(dp[l+1][p][0]+dp[l+1][p][1])*((d[r-1]-d[p])==0))%mod;
                }
            }
            if(r-l>=4&&(s[l]=='('||s[l]=='?')&&(s[r]==')'||s[r]=='?')){
                for(register int p=l+1;p<=min(l+k,r-1);p++){//情况(SA)
                    if(p-l<=k) dp[l][r][0]=(dp[l][r][0]+(dp[p+1][r-1][0]+dp[p+1][r-1][1])*((d[p]-d[l])==0))%mod;
                }
            }
            if(r-l>=2){//对于 ASB 串的优化
                for(register int p=l;p<=min(l+k-1,r);p++){
                    dp[l][r][2]=(dp[l][r][2]+(dp[p+1][r][0]+dp[p+1][r][1])%mod*((d[p]-d[l-1])==0))%mod;
                }
            }
            if(r-l>=4){
                for(register int p=l+1;p<r-1;p++){
                    dp[l][r][1]=(dp[l][r][1]+(dp[l][p][0]%mod*dp[p+1][r][2]%mod)%mod)%mod;
                }
            }
        }
    }
    printf("%lld",(dp[1][n][0]+dp[1][n][1])%mod);
}