题解：CF1630C Paint the Middle

· · 题解

题意

给出一个长度为 n 的序列 a。

还有一个初始为 0 的数组 c。

可以执行以下操作任意次：

选择三个元素 i, j 和 k（1 \leq i < j < k \leq n）。

条件：c_i=c_j=c_k=0 且 a_i=a_k。

效果：c_j=1。

求操作后 \sum\limits_{i=1}^n{c_i} 的最大值。

做法

一眼 DP。

设 f_i 表示区间 1 到 i 的没有贡献的数的个数，lst_i 表示元素 i 第一次在 a_i 中的下标。

初始化，f_1=1，因为第一个怎么操作都不可能有贡献。

对于每一个 i，他可以把 lst_{a_i}+1 到 i-1 赋值，我们枚举 j，其中 \min(lst_{a_i},i-1)\leq j \leq i-1，考虑将 j+1 到 i-1 赋值。所以 f_i=f_j+1，这个 +1 是算上 i 本身无法赋值。

那么 DP 方程式也就呼之欲出：

f_i=\min\limits_{j=\min(lst_{a_i},i-1)}^{i-1}f_j+1

可这 n^2 的时间复杂度肯定过不了，用个线段树维护一下区间最小值就行了。

做蓝题的人应该没有不会线段树吧。

但是，有人要问了，如果 lst_{a_i} 的 c 为 1 你都不知道那不是出锅了吗。

表面上来看，这样的问题确实存在，看似不可做，但仔细一想就可发发现，你总能改变赋值顺序来做到理想的贡献（手模几个样例理解更深）。

Code

#include<bits/stdc++.h>
#define ls(a) a<<1
#define rs(a) a<<1|1
using namespace std;
const int MAXN=1e6+10;
const int INF=1e9+7;
int n,g,a[MAXN],tree[MAXN],lst[MAXN];
//----------------线段树板子（求最小值）------------- 
void push_up(int x){
    tree[x]=min(tree[rs(x)],tree[ls(x)]);
}
void build(int x,int l,int r){
    if(l==r){
        tree[x]=INF;
        return;
    } 
    int mid=(l+r)>>1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
    push_up(x);
}
void update(int ql,int qr,int l,int r,int x,int k){
    if(ql<=l&&r<=qr){
        tree[x]=min(tree[x],k);
        return ;
    }
    int mid=(l+r)>>1;
    if(ql<=mid) update(ql,qr,l,mid,ls(x),k);
    if(qr>mid) update(ql,qr,mid+1,r,rs(x),k);
    push_up(x);
}
int query(int ql,int qr,int l,int r,int x){
    int ans=INF;
    if(ql<=l&&r<=qr) return tree[x];
    int mid=(l+r)>>1;
    if(ql<=mid) ans=min(ans,query(ql,qr,l,mid,ls(x)));
    if(qr>mid) ans=min(ans,query(ql,qr,mid+1,r,rs(x)));
    return ans;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=n;i>=1;i--) lst[a[i]]=i;
    build(1,1,n),update(1,1,1,n,1,1);//初始化，第一个肯定没贡献 
    for(int i=2;i<=n;i++) g=query(min(lst[a[i]],i-1),i-1,1,n,1)+1,update(i,i,1,n,1,g);
    //DP
    printf("%d",n-g);//答案为：总的-没贡献的 
    return 0;
}

完结散花