CF1598F RBS

题目大意

定义括号序列为只包括 \(\texttt{(}\) 和 \(\texttt{)}\) 的字符串。一个匹配的括号序列（简记为 RBS）满足，可以在其中加入 \(1\) 和 \(+\)，将其转化为合法的代数式，例如：

• \(\texttt{()()}\) 和 \(\texttt{(())}\) 是匹配的；
• \(\texttt{)(}\) 和 \(\texttt{(}\) 和 \(\texttt{)}\) 不是。

将两个字符串拼接在一起简记为 \(x+y\)。例如，\(\texttt{()()}+\texttt{)(}=\texttt{()())(}\)。

给定 \(n\) 个括号序列 \(s_1\sim s_n\)，你可以将他们任意重新排序，要求使得最终排序后的字符串满足 \(s_1+\dots+s_n\) 的 RBS 前缀个数最多。

思路

首先考虑把括号序列改写成由 \(1\) 和 \(-1\) 构成的序列，把 \(\texttt{(}\) 看作 \(1\)，\(\texttt{)}\) 看作 \(-1\)。

如果一个括号序列是匹配的，那么它的任意前缀的权值和均为非负，且整个序列的权值为 \(0\)。

如果一个 \(a\) 串能够在后面接一个 \(b\) 串使得形成了更长的括号序列，那么这个 \(a\) 串的权值一定是非负的。\(a\) 串最后可以有多出来的 \(\texttt{(}\)，也可以没有多出的部分，但不能有多出的 \(\texttt{)}\)。

我们设这个 \(a\) 串的权值为 \(x\)，设 \(b_i\) 的最小前缀和为 \(y\)。

1. 假设 \(x+y<0\)，那么说明在 \(a\) 和 \(b\) 拼接成的新串中存在前缀和小于 \(0\) 的前缀，即右括号数量多于左括号，不能再继续往后边加串了。我们造成的贡献是从 \(b\) 串开头到第一个小于 \(0\) 位置之前的部分中，前缀和为 \(-x\) 的位置的个数。也就是说，这里只更新答案，不继续进行转移。

2. 若 \(x+y\geq0\)，说明还能继续向后匹配，我们在更新答案的同时还需要继续向后转移。

考虑状压，开个桶存一下每种前缀和值的数量和第一次出现 \(-x-1\) 之前出现 \(-x\) 的数量，map 会被卡，可以用 unordered_map，内部是用哈希实现（不过可能有人丧心病狂对着模数卡）。

Code

#include <bits/stdc++.h>

using namespace std;

#define lim(x) (1 << x - 1)

const int N = 33;

int n;
int ans = INT_MIN >> 2,sum;

string st[33];

int MinPre[lim(21) + 114],val[N];
int Val[lim(21) + 114];
int dp[lim(21) + 114];

unordered_map<int,int> bucket[N];
unordered_map<int,int> UpdateBucket[N];

bool legal[lim(21) + 114];

int main() {
    cin >> n;
    for(int i = 1;i <= n; i++) {
        cin >> st[i];
        sum = 0;

        for(int j = 0;j < st[i].size(); j++) {
            if(st[i][j] == '(')
                sum += 1;
            else
                sum -= 1;

            MinPre[i] = min(MinPre[i],sum);
            bucket[i][sum] ++;

            if(bucket[i][sum] == 1) 
                UpdateBucket[i][sum] = bucket[i][sum + 1];
        }

        val[i] = sum;
    }

    legal[0] = 1;

    for(int s = 0;s < lim(n + 1); s++) {
        sum = 0;
        
        for(int i = 1;i <= n; i++) 
            if(s & lim(i)) 
                sum += val[i];

        Val[s] = sum;
        // 状态的权值 
    }

    
    for(int s = 0;s < lim(n + 1); s++) {
        if(!legal[s])// 不合法 
            Val[s] = -1;
        
        if(Val[s] < 0) {
            dp[s] = 0;
            continue;
        }

        sum = Val[s];

        for(int i = 1;i <= n; i++) {
            if(s & lim(i))
                continue;
            
            if(sum + MinPre[i] < 0) // 只更新不转移
                ans = max(ans,dp[s] + UpdateBucket[i][-sum - 1]);
            else {// 更新且转移 
                legal[s | lim(i)] = 1;
                dp[s | lim(i)] = max(dp[s | lim(i)],dp[s] + bucket[i][-sum]); 
            }
        }
    }

    for(int s = 0;s < lim(n + 1); s++)
        ans = max(ans,dp[s]);
    
    cout << ans;
    return 0;
}