CF1556C Compressed Bracket Sequence题解

· · 题解

纪念拿到最优解，写一篇题解。

首先这题我们有一个很显然的想法：设一个 sum 表示当前有多少个左括号未匹配。当我们到一个奇数位置时 sum 加上 c_i ,否则sum 减去 c_i，ans 加上 c_i。

但这样有一种情况我们就会算漏。考虑这样一个括号序列 \text{()()}，按照我们 上面的算法得到的 答案是 2，但实际有 \text{()}、 \text{()}、 \text{()()} 这三个合法序列。

为社么会错呢？因为我们在用上面算法的时候默认计算的序列都是首尾配对的即类似 \text{(s)} 这样的序列，我们漏掉了\text{(s)(s)} 这样的序列。因此，我们可以再设一个数组 f，f_i 表示以 i 结尾的合法序列，即把 c_i 个右括号都匹配完后，构成的合法序列数就为 f_i，每次更新 ans 的时候再加上 f_i 就好了。

那么设 pre 为与 c_i 中最后一个括号匹配的位置,若 c_i 没用完则不更新

f_i = \begin{cases} f_{\text{pre}}+1 & \text{pre}>0\\ 0 & \text{otherwise.} \end{cases}

那么这道题就做完了，接下来是代码时间 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e3+5;
ll ans,f[maxn];
int n,tot;
int c[maxn],st[maxn];//开个栈来记录还有左括号的位置
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    for(int i=1;i<=n;i++){
        if(i&1)
            st[++tot]=i;
        else{
            int las=0;
            for(int j=tot;j>=1;j--){
                if(c[i]>=c[st[j]]){
                    las=st[j]-1;//las会被不断更新，直到c[i]被减到0。
                    ans+=c[st[j]]+f[st[j]-1];
                    c[i]-=c[st[j]];
                    c[st[j]]=0;
                    --tot;
                }
                else{
                    ans+=c[i];
                    c[st[j]]-=c[i];
                    c[i]=las=0;//如果在匹配的时候，pre还有i没了，此时不能从f[las]转移过来
                    if(!c[st[j]])
                        --tot;
                    break;
                }
                if(!c[i])
                    break;
            }
            if(!c[i])
                f[i]=f[las]+1;//如果右括号都用完了就更新f
        }
    }
    printf("%lld\n",ans);
    return 0;
}