CF1598F RBS 题解

题意

给 \(n\) 个串，求将这 \(n\) 个串以任意顺序接起来的最大的是合法括号序列的前缀数。

分析

\(n\) 很小，考虑状压 dp。

有一个很典的转化是将 （ 看成 \(+1\)，将 ) 看成 \(-1\)，于是问题就转化成求将 \(n\) 个只含 \(+1,-1\) 的序列任意接起来的最大合法前缀数，合法前缀的定义为处处前缀和非负，且该前缀总和为 \(0\)。

发现对于选中几个串安排好，无论前面是怎么排的都不对后面有影响，因为排好部分的总和一定。\(dp_{S,0/1}\) 表示已经在前面安排好的字符串状态为 \(S\) ，存在前缀和小于 \(0\) / 不存在时的最大合法括号序列数。设前面排好的总和为 \(pre\)，对于每一个串预处理一下前缀 \(\min\)，二分找到第一个 \(+pre<0\) 的位置，再二分求出在该位置前的 \(=-pre\) 的前缀和数 \(cnt\)，直接转移即可。

核心代码

const int MAXN=21;
const int MAXM=4e5+7;
const int _=4e5;
int n,dp[1<<MAXN][2],sum[1<<MAXN],pr[MAXN][MAXM],mn[MAXN][MAXM];string s[MAXN];
vector<int>vec[MAXN][MAXM+MAXM];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;int i,j,mask,tmp;for(i=0;i<n;i++) cin>>s[i];mem(dp,0xcf);dp[0][1]=0;
    for(i=0;i<n;i++){
        pr[i][0]=(s[i][0]=='('?1:-1);mn[i][0]=-pr[i][0];
        vec[i][pr[i][0]+_].emplace_back(0);
        for(j=1;j<s[i].size();j++){
            pr[i][j]=pr[i][j-1]+(s[i][j]=='('?1:-1);
            mn[i][j]=-qmin(-mn[i][j-1],pr[i][j]);
            vec[i][pr[i][j]+_].emplace_back(j);
        }
    }for(mask=1;mask<(1<<n);mask++) 
        for(i=0;i<n;i++) if(mask&(1<<i)) sum[mask]+=pr[i][s[i].size()-1];
    for(mask=1;mask<(1<<n);mask++){
        for(i=0;i<n;i++){
            if(!(mask&(1<<i))) continue;tmp=mask^(1<<i);
            int pre=sum[tmp];bool flag=true;if(pre-mn[i][s[i].size()-1]<0) flag=false;
            int p=upper_bound(mn[i],mn[i]+s[i].size(),pre)-mn[i],cnt=0;
            if(vec[i][-pre+_].empty()||vec[i][-pre+_].front()>=p) cnt=0;
            else if(vec[i][-pre+_].back()<p) cnt=vec[i][-pre+_].size();
            else cnt=lower_bound(vec[i][-pre+_].begin(),vec[i][-pre+_].end(),p)-vec[i][-pre+_].begin();
            if(flag){
                dp[mask][1]=qmax(dp[mask][1],dp[tmp][1]+cnt);
                dp[mask][0]=qmax(dp[mask][0],dp[tmp][0]);
            }else dp[mask][0]=qmax(dp[mask][0],dp[tmp][0],dp[tmp][1]+cnt);
        }
    }printf("%d\n",qmax(dp[(1<<n)-1][0],dp[(1<<n)-1][1]));
    return 0;
}

record