2020牛客跨年ak赛 F.开心消消乐(括号匹配+预处理)

传送门

这里只说的把,也就是暴力枚举删除区间

似乎有更快的算法,以后再补

当删除某段区间后,最终剩下一段前缀和一段后缀作括号匹配

会自动消除

对于一段序列来说消除的顺序是不影响最终的结果的

不妨先对前缀做括号匹配,变成的形式

对后缀也做括号匹配,变成的形式

不难发现,此时能消除的只剩下前缀后面的连续零和后缀前面的连续一

所以直接预处理这两部分,还要预处理前缀自己匹配剩下的长度和后缀剩下的长度

用栈模拟括号匹配即可

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,top,pre[maxn],pre0[maxn],suf[maxn],suf1[maxn];
int o[maxn],z[maxn];
char a[maxn],q[maxn];
int main()
{
    cin >> n >> (a+1);
    int zero = 0;
    for(int i=1;i<=n;i++)
    {
        o[i] = o[i-1]+(a[i]=='1');
        z[i] = z[i-1]+(a[i]=='0');
        if( !top )    q[++top] = a[i],zero = ( a[i]=='0' );//栈空,没问题 
        else    
        {
            if( q[top]=='0'&&a[i]=='1' )    top--,zero--;
            else//不能消除,栈顶是0自己也是0，栈顶是1自己是0或1 
                q[++top] = a[i], zero += ( a[i]=='0' );
        }
        pre[i] = top, pre0[i] = zero;
    }
    int ans = top;
    int one = 0; top = 0;
    for(int i=n;i>=1;i--)
    {
        if( !top )    q[++top] = a[i], one = ( a[i]=='1' );
        else
        {
            if( q[top]=='1'&&a[i]=='0' )    top--,one--;
            else
                q[++top] = a[i], one += ( a[i]=='1' );
        }
        suf[i] = top, suf1[i] = one;
    }
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
    {
        if( o[j]-o[i-1]!=2*(z[j]-z[i-1]) )    continue;
        ans = min( ans,pre[i-1]+suf[j+1]-min( pre0[i-1],suf1[j+1])*2 ); 
    }
    cout << ans;
    return 0;
}