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

· · 题解

赛时想了好久，真难吧。不过感觉远小于 C（不会组合数学导致的）。

solution

考虑所有保留下来的值，它们是不能被删除的，下文把这些位置称为关键点。

令序列中有 m 个 0，那么关键点个数为 n-m\times 2。

考虑连续两个关键点间形成的区间，这个区间需要被删空，那么对于这个区间的每个后缀，令 c_0 为后缀中 0 的数量，c_1 为非 0 的数量，则必有 c_0\ge c_1。

原因是如果有一个后缀 c_0<c_1，那么这个后缀中的有值的元素就不可能被删空，显然不符合上述条件。

对于最后一个关键点以后的区间同样需要满足每个后缀 c_0\ge c_1，原因同上。对于第一个关键点之前的区间是不需要满足的，因为可以通过后面的 0 删除最前端来将最前面删空。

可以发现所选的关键点集合满足以上条件就符合题意了，构造出来也不难，每个区间的 0 将这个区间的元素全部删掉，多余的 0 再把队首的元素删掉即可，我们需要所选关键点的点权和最大。

我们可以预处理出所有合法的区间，对于 i，区间 [j+1,i-1] 满足上面的条件，则 j 显然是 [1,i-1] 的一个后缀，mn_i 为满足 [j+1,i-1] 是一个合法区间的 j 的最小值。

令 f_{i,j} 表示枚举到 i，已经选了 j 个关键点的点权和最大值。转移方程为 f_{i,j}=\max_{k=mn_i}^{i-1}{f_{k,j-1}+a_i}。

用树状数组优化一下可以做到严格 O(n^2\log n)，但是赛时我直接枚举 k 也可以通过，不知道复杂度有没有保证。

实现时可以钦定 n+1 为关键点，从而不用讨论最后一个关键点在哪个位置。

:::info[code]

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
const int N=1e3+10;
const int inf=1e9+10;

inline void read(int &x) {
    x=0;
    char ch=getchar();
    while (ch<48) ch=getchar(); 
    while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}

int n,m;
int a[N],mn[N];

struct BIT {
    ll v[N];
    inline void add(int p,ll k) {for(;p<=n+2;p+=(p&-p))v[p]=max(v[p],k);}
    inline ll qry(int p){ll r=0;for(;p;p-=(p&-p))r=max(r,v[p]);return r;}
}tr[N];

int main() {
    read(n);
    f(i,1,n) read(a[i]),m+=(!a[i]);m*=2;
    f(i,1,n+1) {
        int c0=0,c1=0;
        F(j,i-1,1) {
            if (c0<c1) break;
            if (!a[j]) c0++;
            else c1++;
            mn[i]=j;
        }
    }
    f(i,1,n+1) {
        F(j,n-m+1,2) {
            ll res=tr[j-1].qry(n-mn[i]+2)+a[i];
            tr[j].add(n-i+2,res);
            if (i==n+1&&j==n-m+1) printf("%lld\n",res);
        }
        tr[1].add(n-i+2,a[i]);
    }
    if (n==m) puts("0");
    return 0;
}

:::