题解 P6827 【「EZEC-4」括号】

· · 题解

Update 10.13 博客上代码不知道哪里挂了/fad，本地改了博客上可能忘改了？被dalao指出，现已更正。

P0：题外话

讲个笑话，正解状压。

P1：基础观察

首先需要证明一个结论：如果某一个括号串在点 i 出发有不止一个完全匹配，那么选择结束点最小的匹配一定最佳。

因为我们规定了只有完全匹配完某个字符串才能继续匹配，所以答案一定是越早匹配完越好。

P2:题解

下文用 k 表示 len(k), a 表示 len(a)。

对于 a\le 8 的数据，暴力枚举每种可出现的排列查最大值，ans 取 max 即可

复杂度 O(na^a)。

对于 n \le 10 且随机的数据，考虑优化全排列。

发现可以使用 dfs 进行枚举，每当枚举到就退出。

复杂度 O(na^a)，但在数据随机下能够过（良心出题人）。

核心枚举代码: by @Ecrade_

void dfs(ll pos,ll id,ll cur){
    ans = max(ans,cur);
    if (pos >= l) return;
    for (ll cnt = 0;cnt < xl[id] && pos < l;pos += 1)
        if (x[id][cnt] == k[pos]) cnt += 1,cur += v[id];
    for (ll i = 1;i <= n;i += 1) dfs(pos,i,cur);
}

对于 n \le 10 且每个字符只用一次的数据，发现可以对每个位置进行状压。

首先预处理在每个位置时分别处理后面第一次出现 ( 和 ) 的位置，此操作用倒叙枚举能够快速的求出。

for (int i=k;i>0;i--){
    nxt[0][i] = (s[i-1]=='(') ? i : nxt[0][i+1];
    nxt[1][i] = (s[i-1]==')') ? i : nxt[1][i+1];
}
dp[i][j]$ 表示目前匹配到 $i$ 点，字符串存取数量为 $j$。枚举每个串暴力查 $k$ 进行转移即可，复杂度 $O(n2^nak)

核心转移代码：

inline void solve(int kk, int type, int pos){
  int cnt = 1, val = dp[type][kk];
  while(cnt<=a[pos].length()){
    int now = (a[pos][cnt-1])==')';
    if (!nxt[now][kk]) {ans = max(ans,val);return;}//没地方跳了
    if (cnt==a[pos].length()) val+=v[pos],dp[type+(1<<(pos-1))][nxt[now][kk]+1] = max(dp[type+(1<<(pos-1))][nxt[now][kk]+1],val);//跳完了
    else kk = nxt[now][kk]+1,val+=v[pos];
    cnt++;
  }
  ans = max(ans,val);
}

另一种可行的方法为在每个位置进行 dp，在每个位置均暴力枚举字符串找匹配 (后面会具体讲 dp 思路，这里略)。

复杂度 O(nk^2)，人口普查。

对于 n\le 100,a \le 8 的数据，考虑暴力 dp。

令 dp[i] 表示在点 i 前能拿到的最高完美匹配，注意 dp[i] 不包括点 i 能拿到的。

转移可以枚举括号串，对每个括号串暴跳预处理出来的括号。

转移代码：

inline void jump(int kk, int pos){
  int cnt = 1, val = dp[kk];
  while(cnt<=a[pos].length()){
    int now = (a[pos][cnt-1])==')';//转化为01
    if (nxt[now][kk]==-1) {ans = max(ans,val);return;}//没地方跳了
    if (cnt==a[pos].length()) dp[nxt[now][kk]+1] = max(dp[nxt[now][kk]+1],val+v[pos]);//跳完了
    else kk = nxt[now][kk]+1,val+=v[pos];
    cnt++;
  }
  ans = max(ans,val);
}

复杂度 O(k+nak)

对于 a \le 8 的数据，暴力可过，但有另外的解法（近似正解）

发现括号只有两种形态，考虑用 01 表示，从而想到状压。

在预处理 () 的位置后我们还可以暴力预处理每一种状态。预处理的东西跟之前意义一样，对于每个字符暴跳 ( 和 ) 即可。极限状态数 2^{a}-1，预处理后暴跳可以做到 O(a) 处理出某一个状态在某一个点的值。

之后 dp 转移可以暴力枚举字符串转移,对于长度为 a 的字符串直接转移，否则暴力枚举进行转移。

复杂度 O(k+a2^ {a}k+nka) 怎么好像还慢了

可以考虑枚举每种长度进行状压，于是时空变为 O(k+a^22^ak+nk)

对于 a \le 300 的数据，暴力复杂度错误，考虑状压。

然而直接状压 a 显然是个笑话，于是考虑分块思想。

发现可以将每个括号串进行分块处理。分成 \sqrt{a} 块，

只需预处理长度为 \sqrt{a} 的字符串即可。

对于转移，在每个点上仍然暴力枚举字符串，但我们对字符串分块跳跃。对于不足 \sqrt{a} 长度的块暴跳即可。

然而发现这还是过不去

发现块长使复杂度不平衡, 瓶颈在于状压的状态，因此，我们可以尝试调节块长。

复杂度 O(k+\sqrt{a}2^ {\sqrt{a}}k+nk\sqrt{a}),实测块长 4\sim8 都可过。

const int MAXN = 505;
const int MAXK = 1e4+5;
const int L = 5;
int n,v[MAXN],nxt[2][MAXK],dp[MAXK],k,pre[MAXK][(1<<L)+5],num[MAXN],cor[MAXN][(MAXN/L)+1],ans;
string s,a[MAXN];
int max(int a, int b){return a>b?a:b;}
int solve(int pos, int num, int val){
  while(true){
    int now = (num>>val) & 1;
    if (!nxt[now][pos]) return 0;
    if (val==0) return nxt[now][pos];
    pos = nxt[now][pos]+1;val--;
  }
}
inline int get(int pos, int f, int t){
  int re = 0;
  for (int i=f;i<=t;i++) re += ((a[pos][i]=='(') ? 0 : 1) * (1<<(t-i));
  return re;
}
void jump(int pos, int ptr,int cnt,int sum, int from){
  if (cnt>a[pos].length()) {dp[ptr] = max(dp[ptr],dp[from]+sum);return;}
  while(cnt<=a[pos].length()){
    int now = (a[pos][cnt-1])==')';
    if (!nxt[now][ptr]) {ans = max(ans,dp[from]+sum);return;}//没地方跳了
    ptr = nxt[now][ptr]+1,sum+=v[pos];
    cnt++;
  }
  if (ptr!=-1)dp[ptr] = max(dp[ptr],dp[from]+sum);//跳完
  ans = max(ans,dp[from]+sum);
}
// pos是块的编号,cor是目前块的括号序列
void Solve(int kk, int pos){
  int re = 0,from = kk,cnt = 1;
  for (int i=1;i<=num[pos];i++){
    if (pre[kk][cor[pos][i]]) {    // 如果有块可以跳
      kk = pre[kk][cor[pos][i]]+1;
      re += L*v[pos];
      cnt+=L;
    }else break;
  }
  jump(pos,kk,cnt,re,from);
}
signed main(){
  cin >> n >> s;
  k = s.length();
  for (int i=1;i<=n;i++) cin >> a[i] >> v[i];
  for (int i=1;i<=n;i++) {
    num[i] = (a[i].length()/L);
    for (int l=1;l<=num[i];l++) cor[i][l] = get(i,L*(l-1),L*l-1);
  }
  for (int i=k;i>0;i--){
    nxt[0][i] = (s[i-1]=='(') ? i : nxt[0][i+1];// 0表示 (, 1表示 )
    nxt[1][i] = (s[i-1]==')') ? i : nxt[1][i+1];
  }
  for (int i=1;i<=k;i++)
    for (int j=0;j<=(1<<L)-1;j++)
      pre[i][j] = solve(i,j,L-1);  //处理状态
  for (int i=1;i<=k;i++)
    for (int j=1;j<=n;j++)
      Solve(i,j);
  printf("%d\n",ans);
}
/*
3
((()())(()()
(() 4
() 2
()()()() 5
*/

审题人给出了对不足大小的块不足长度时不需暴跳的方法：

令 pre[l][i][j] 为长度 l 的块在使用 i 号字符串，状态为 j 的最早完美匹配结束点。这个长度在 solve 函数内可以求出，总复杂度不变，但暴跳时直接处理即可。

对于不是完美匹配的块，我们将 pre[l][i][j] 内的值变为在某个长度下最多能拿的匹配数量。为了区分结束点与长度，我们可以将这个数字设为负数，然后在累计时乘以 -1 即可。

然而不知道为啥我这么写跑得更慢了，代码不贴了，有兴趣可以找我要。

P3：可能存在的疑惑

为什么 std 在块大小不足 \sqrt{a} 时要暴力转移呢？

可以发现，假设块大小为 8，用 0 表示 (，1 表示 )，则 (((((((( 的表示法为 0000000, 即 0。

然而，对于大小为 6 的小块，(((((( 的表示法同为 0，但两者代表的东西不同。故我们不能直接使用状态进行转移。