trie上记忆化搜索，括号匹配——cf1152D好题！

佚名 6年前 (2019-04-25) 随笔 2040人围观抢沙发百度已收录

一开始以为是卡特兰数的性质，，后来发现其实是dp，但是用记忆化搜索感觉更方便一点
先来考虑字典树上的问题
设要求的序列长度是2n，我们用二元组(a,b)来表示前面长为a的序列中出现的 '(' - ')' = b
那么可以得知所有的符合这种要求的前缀的后缀形成的trie都是相同的
那么我们用二元组(i,j)来表示长为i的后缀中 ')' - '(' = j
只要这样一棵trie的最大匹配，就可以推出i+1的最大匹配

用dp[i][j]表示子树是二元组(i,j)对应的trie的最大匹配数
然后再来看最大匹配的问题：
    每个结点只能选择一个子节点进行匹配，并且这个子节点不能再和下面一层匹配了
    那么从底层往上考虑，2n层肯定没有匹配，2n-1层选一个叶子节点匹配，那么2n-2就没有匹配了
    依次类推，可以发现奇数层的结点可以选一个子节点进行匹配，偶数层就没有匹配了 
所以状态转移方程是：
    因为是倒序往上的,dp[i][j]=dp[i-1][j+1]+dp[i-1][j-1]+(i%2==0)*flag，flag是子树个数

#include<bits/stdc++.h>
using namespace std;
#define maxn 2005
#define ll long long 
#define mod 1000000007
ll n,dp[maxn][maxn];
int dfs(int i,int j){
    if(dp[i][j]!=-1)return dp[i][j];
    if(i==0){//长度为0时，差值也要为0 
        if(j==0)return dp[i][j]=0;
        else return dp[i][j]=-2;    
    }
    if(i<j || j<0)return dp[i][j]=-2;
    int flag=0;
    ll res1=dfs(i-1,j+1),res2=dfs(i-1,j-1);
    if(res1>=0)flag++;else res1=0;
    if(res2>=0)flag++;else res2=0;
    
    dp[i][j]=(res1+res2+(i%2==0)*flag)%mod;
    if(flag)return dp[i][j];
    return dp[i][j]=-2;
}
int main(){
    cin>>n;
    memset(dp,-1,sizeof dp);
    cout<<dfs(2*n,0)<<endl;
    //    cout<<dp[5][1]<<endl;
}