题解：CF2018D Max Plus Min Plus Size

· · 题解

一道很妙的题。动态 DP。

首先，一个很显然的想法是令 f_{i,j,k,0/1} 表示考虑前 i 个数，红数最小值为 j，红数最大值为 k，第 i 个数不涂/涂红时的最大红数数量。枚举前 i-1 个最小值/最大值来转移，时间复杂度 O(n^4)。

考虑优化。显然这个状态数就有很大问题，所以我们必须减少状态数量。根据数学直觉，最优解里面一定有一个染色方案染红了至少一个全局最大值。我们取任意一个染色方案，其染红的数下标集合为 S，如果它不包含任何一个全局最大值，那么我们假设有一个全局最大值 a_i，考虑染色集合 (S-\{i-1\}-\{i+1\})\cup\{i\}，它符合不能相邻的条件，且 \Delta\min\ge 0,\Delta\max\ge 1,\Delta\text{ size}\ge -1，从而答案不会更小。

从而，我们可以钦定红数的 \max 就是全局最大值 mx。接下来，我们从大到小枚举红数的 \min，然后求出“mx 至少染红一个，所有小于 \min 的数均不能染红，染红的数不能相邻”情况下染红数最大个数。如果暴力做依然是 O(n^2) 的，不行。我们考虑每次减小 \min 之后带来的影响，实际上就是一些原本必定不能染红的变成可染可不染了。我们维护每一个连通块 i:[l,r]，令 f_{i,0/1,0/1,0/1} 表示连通块 i 左端点 l 不染/染，右端点 r 不染/染，此连通块内没有/有强制将一个 mx 染红。那么，令 e_i=\max\{f_{i,*,*,0}\},h_i=\min\{e_i-f_{i,*,*,1}\}，最大的染色个数就是 (\sum e_i)-\min\{h_i\}。e_i 在合并的时候直接维护即可。至于 h_i，其实它要么是 inf（即这个区间不存在 mx），要么是 0,1（若这个区间有 mx，且所有最大化染色个数的方案都不包括全局最大值 mx，那么一定是 l,r 同奇偶，最大化染色个数的方案是将与 l,r 同奇偶的所有点染色，共计 (r-l+2)/2 个，那么我们取原本染色集合的补集就一定染了 mx，且染色个数仅减少了 1），所以我们开两个桶记录一下 0,1 的个数即可。时间复杂度 O(n\alpha(n))。

为了省事，我写的代码是 O(n\log n) 的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int _=4e5+5,inf=1e9;
multiset<int>d;
int f[_][2][2][2],a[_],b[_],v[_],l[_],r[_],h[_],e[_],c,s,mx,w,n,T;
map<int,vector<int> >p;
int g(int x){
    return b[x]==x?x:b[x]=g(b[x]);
}
inline void del(int x){
    multiset<int>::iterator u=d.lower_bound(x);
    if(u!=d.end()&&(*u)==x)d.erase(u);
}
inline void mer(int x,int y){
    b[x]=b[y]=++c;l[c]=l[x];r[c]=r[y];
    del(h[x]);del(h[y]);s-=e[x];s-=e[y];
    h[c]=inf;e[c]=0;
    for(int i:{0,1})
        for(int j:{0,1})
            for(int k:{0,1})
                for(int I=0;I<2-k;I++)
                    for(int J:{0,1})
                        for(int K:{0,1})f[c][i][j][J|K]=max(f[c][i][j][J|K],f[x][i][k][J]+f[y][I][j][K]);
    for(int i:{0,1})
        for(int j:{0,1})e[c]=max(e[c],f[c][i][j][0]);
    for(int i:{0,1})
        for(int j:{0,1})h[c]=min(h[c],e[c]-f[c][i][j][1]);
    d.insert(h[c]);s+=e[c];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;mx=w=s=0;c=n;p.clear();d.clear();
        for(int i=1;i<=n;i++){
            cin>>a[i];v[i]=0;
            e[i]=1;l[i]=r[i]=i;
            mx=max(mx,a[i]);
            p[-a[i]].push_back(i);
        }
        for(int i=1;i<n+n;i++){
            b[i]=i;
            for(int j:{0,1})
                for(int k:{0,1})
                    for(int I:{0,1})f[i][j][k][I]=-inf;
        }
        for(int i=1;i<=n;i++)
            if(a[i]==mx){
                h[i]=0;
                for(int j:{0,1})f[i][j][j][j]=j;
                f[i][1][1][0]=1;
            }else{
                h[i]=inf;
                for(int j:{0,1})f[i][j][j][0]=j;
            }
        for(auto i:p){
            for(int j:i.second){
                d.insert(h[j]);s+=e[j];
                if(j>1&&v[j-1])mer(g(j-1),g(j));
                if(j<n&&v[j+1])mer(g(j),g(j+1));
                v[j]=1;
            }
            w=max(w,mx-i.first+s-*d.begin());
        }
        cout<<w<<'\n';
    } 
    return 0;
}