题解：P10600 BZOJ4350 括号序列再战猪猪侠

Redamancy_Lydic · 2024-10-28 20:20:50 · 题解

根据题目要求，容易想到区间计数动态规划。

我们只考虑左括号，设 dp_{l,r} 表示当前考虑从第 l 到第 r 个左括号时的方案数，注意，这里的状态同时包含了这些左括号对应的右括号。

考虑转移，我们设 A 为一个合法括号串，它表示的左括号区间是 [l,r]，可以很自然的分三种情况：

• (A)，此时需满足 [l,r] 中所有右括号都没有要求大于第 l-1 个左括号的右括号的限制。

• ()A，此时和上面类似，需满足 [l,r] 中所有右括号都没有要求小于第 l-1 个左括号的右括号的限制。

• (A，同时把 A 从中间断开插入右括号，设当前枚举的断点为 k，此时需满足 [l,k] 中所有右括号都没有要求大于第 l-1 个左括号的右括号的限制，以及 [l-1,k] 中所有右括号都没有要求大于区间 [k+1,r] 中所有左括号的右括号的限制。

对于这些限制的快速判断我们可以维护一个矩阵，每条信息相当于矩阵上的一个点，这样对于前文的要求可以快速用二位前缀和的值的存在与否判断是否全部满足。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int w=1,s=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
    return w*s;
}
const int mod=998244353;    
const int maxn=500+10;
const int inf=1e13+7;
int n,m;
int dp[maxn][maxn],sum[maxn][maxn],a[maxn][maxn];
int ask(int l1,int r1,int l2,int r2)
{return sum[l2][r2]-sum[l1-1][r2]-sum[l2][r1-1]+sum[l1-1][r1-1];}
void Main()
{
    n=read(),m=read();
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)a[i][j]=sum[i][j]=0;
    bool ff=1;
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        a[x][y]=1;
        if(x==y)ff=0;
    }
    if(!ff){puts("0");return ;}
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++)dp[i][i]=1;
    for(int len=2;len<=n;len++)
    {
        for(int l=1;l<=n-len+1;l++)
        {
            int r=l+len-1;
            if(!ask(l,l+1,l,r))(dp[l][r]+=dp[l+1][r])%=mod;
            if(!ask(l+1,l,r,l))(dp[l][r]+=dp[l+1][r])%=mod;
            for(int k=l+1;k<r;k++)
            { 
                if(!ask(l,l+1,l,k)&&!ask(k+1,l,r,k))
                {
                    dp[l][r]=(dp[l][r]+dp[l+1][k]*dp[k+1][r]%mod)%mod;
                }
            }
        }
    }
    printf("%lld\n",dp[1][n]);
}
signed main()
{
#ifdef Lydic
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
//  #else
//      freopen("Stone.in","r",stdin);
//      freopen("Stone.out","w",stdout);
#endif
    int T=read();
    while(T--)Main();
    return 0;
}