题解：P17296 [ICPC 2026 Xi'an I] Palindromic and Balanced

· · 题解

题意简述

求给定括号串的最长子序列。该子序列需要是合法括号序列，且删去首尾字符后为回文串。

解题思路

非空答案的首字符只能是 (，末字符只能是 )。把这两个字符删去，记剩余回文串为 t，长度为 m。将左括号记作 1，右括号记作 -1，并设 b_i 为 t 的前 i 项之和。

完整答案是合法括号序列，所以在进入末尾右括号前，所有前缀都不能低于 0。去掉开头贡献的 1 后可得 b_i\ge-1，并且 b_m=0。

由于 t 是回文串，最后 i 项与最前 i 项相同，其和也是 b_i。总和为 0，因此 b_{m-i}=-b_i。又有 b_{m-i}\ge-1，故 b_i\le1。

于是每个 b_i 都位于 [-1,1]。当 i 为偶数时，b_i 也必须是偶数，只能等于 0。因此，把 t 从左到右每两个字符分组，每组只能是 () 或 )(。

回文会把最左一组倒序映到最右一组。因此，首尾两组的类型必定相反。递归删除首尾两组后，内部仍满足相同条件。合法的 t 恰好由以下规则生成：

设 f_{l,r} 表示区间 [l,r] 内，满足上述规则的最长子序列长度。若最优子序列不选某个端点，可以从 f_{l+1,r} 或 f_{l,r-1} 转移。

若 s_l=s_r，还可以把这两个字符作为新结构的最外层字符。此时需要在它们内侧各选一个相反括号，才能组成类型相反的首尾两组。

预处理每个位置前后最近的两种括号。设 l 右侧最近的相反括号在 x，r 左侧最近的相反括号在 y。若 x<y，转移为：

f_{l,r}=\max(f_{l,r},f_{x+1,y-1}+4)

取最靠左的 x 与最靠右的 y，会留下包含其他选择所得区间的内部区间。子序列最优值关于区间包含关系单调，因此不会损失答案。

这些转移只会产生递归规则允许的字符串。反过来，任取一个最优子序列。若它缺少某个区间端点，舍弃端点的转移会保留它。若它同时使用两端，其首尾两组必然由两个同字符端点与两个相反字符组成；最近位置留下的内部区间更大，归纳可知对应转移不会更差。

按区间长度递增计算 f。枚举内部区间 [l,r] 时，若左侧存在 ( 且右侧存在 )，便用 f_{l,r}+2 更新完整答案。内部为空的 () 单独统计。

每组数据的时间复杂度为 O(n^2)，空间复杂度为 O(n^2)。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=5005;
int f[N][N],pre[N][2],nxt[N][2];
void solve()
{
    int n;
    string s;
    cin>>n>>s;
    s=' '+s;
    pre[0][0]=pre[0][1]=0;
    for(int i=1;i<=n;i++)
    {
        pre[i][0]=pre[i-1][0];
        pre[i][1]=pre[i-1][1];
        pre[i][s[i]==')']=i;
    }
    nxt[n+1][0]=nxt[n+1][1]=n+1;
    for(int i=n;i>=1;i--)
    {
        nxt[i][0]=nxt[i+1][0];
        nxt[i][1]=nxt[i+1][1];
        nxt[i][s[i]==')']=i;
    }
    int ans=0;
    for(int i=1;i<=n;i++)if(s[i]==')'&&pre[i-1][0])ans=2;
    for(int k=1;k<=n;k++)
    {
        for(int i=1,j=k;j<=n;i++,j++)
        {
            f[i][j]=max(f[i+1][j],f[i][j-1]);
            if(s[i]==s[j])
            {
                int c=s[i]=='(';
                int x=nxt[i+1][c],y=pre[j-1][c];
                if(x<y)f[i][j]=max(f[i][j],f[x+1][y-1]+4);
            }
            if(pre[i-1][0]&&nxt[j+1][1]<=n)ans=max(ans,f[i][j]+2);
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}