题解：P16350 「Gensokyo OI Round 1」隙间插曲

sbno333 · 2026-04-25 21:27:58 · 题解

这题可以随便 O(n^2) 过吧。

考虑随便刻画一下，容易删除队头的影响一定是一个前缀，队尾则是后面的一些元素。

后者看着好难啊！

我们假设已经确定最终序列删除了哪些，尝试判断是否合法。

发现对于没删除的数，似乎包含一些信息，因为我们删除不能跨过去。

于是我们考虑每个删除的连续段。

我们设 a_i>0 是 (，否则是 )，发现这个段必须形成一个合法括号序列（如果不合法，要么 ) 不足，此时做不到，或者 ) 太多，这时候我们删掉多的部分，那些多的部分肯定是投给删队头了，然后还是合法括号序列）。

进一步的，我们连续段还可以分割，划分成最多的合法括号序列，于是考虑从 i 出发，往后扫，以 i 开头 j 结尾的合法段只有一个合法的 j。

于是我们就能高高兴兴的 DP 了，设 dp_{i,j} 表示考虑了 i 开头的后缀，并且已经投给队头 j 个 0 的最小删除和。

统计就每次算完 dp_i 后看一下如果前面全是作为删队头删的那么怎么贡献答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[1009][1009];
int a[1000009];
int s[1000009];
signed main(){
    int n;
    cin>>n;
    int ze;
    ze=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+(a[i]==0?-1:1);
        ze+=(a[i]==0);
    }
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=n;j++){
            dp[i][j]=1e18;
        }
    }
    dp[n+1][0]=0;
    int ans;
    ans=0;
    for(int i=1;i<=n;i++){
        if(!ze){
            break;
        }
        if(a[i]){
            ze--;
            ans+=a[i];
        }
    }
    for(int i=n;i>=1;i--){
        if(a[i]){
            int c,ss;
            c=ss=0;
            for(int z=i;z<=n;z++){
                if(a[z]){
                    c++;
                    ss+=a[z];
                }else{
                    c--;
                }
                if(c==0){
                    for(int j=0;j<=n;j++){
                        dp[i][j]=dp[z+1][j]+ss;
                    }
                    break;
                }
            }
            for(int j=0;j<=n;j++){
                dp[i][j]=min(dp[i][j],dp[i+1][j]);
            }
        }else{
            for(int j=1;j<=n;j++){
                dp[i][j]=dp[i+1][j-1];
            }
        }
        int sum;
        sum=0;
        for(int j=1;j<i;j++){
            sum+=a[j];
        }
        sum+=dp[i][s[i-1]];
        ans=min(ans,sum);
    }
    int sum;
    sum=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
    }
    cout<<sum-ans;
    return 0;
}