题目概述

CF1479B1 & CF1479B2

解题报告

在本算法下，B1和B2其实没有很大区别，所以下面仅讨论最小值。

定义 $f_{i,0/1,x}$ 表示 $i$ 放了 $0/1$ 颜色，并且另一种颜色的上一个数字是 $x$ 时的答案最小值。

然后考虑转移（设 $a_0=0$ ）：

• 当前 $0$ 前面 $1$ ：$f_{i-1,1,x}+[x\not=a_i]\to f_{i,0,a_{i-1}}$
• 当前 $0$ 前面 $0$ ：$f_{i-1,0,x}+[a_{i-1}\not=a_i]\to f_{i,0,x}$
• 当前 $1$ 前面 $0$ ：$f_{i-1,0,x}+[x\not=a_i]\to f_{i,1,a_{i-1}}$
• 当前 $1$ 前面 $1$ ：$f_{i-1,1,x}+[a_{i-1}\not=a_i]\to f_{i,1,x}$

初值：$f_{0,0,0}=f_{0,1,0}=0$ ，其余为 $INF$ 。

如果把 $f$ 用 $0/1$ 两棵线段树以 $x$ 为下标存下来，我们发现实际上要完成三个操作：整体加 $[a_{i-1}\not=a_i]$ 、查询最小值后单点修改 $f_{i,0/1,a_{i-1}}$ 。

所以用线段树维护DP，最后答案就是 $min\{f_{n,0/1,x}\}$ 。

示例程序

代码也以最小值为例。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000,maxt=maxn<<2;

int n,a[maxn+5],ans;
int MIN[2][maxt+5],tag[2][maxt+5];

inline void Pushup(int p){
    MIN[0][p]=min(MIN[0][p<<1],MIN[0][p<<1|1]);
    MIN[1][p]=min(MIN[1][p<<1],MIN[1][p<<1|1]);
}
void Build(int L,int R,int p=1){
    if (L==R) {MIN[0][p]=MIN[1][p]=(L==0?0:1e9);return;}
    int mid=L+(R-L>>1);Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
    Pushup(p);
}
void Addtag(int tp,int p,int k) {MIN[tp][p]+=k;tag[tp][p]+=k;}
void Pushdown(int p){
    for (int t=0;t<2;t++)
        if (tag[t][p]) Addtag(t,p<<1,tag[t][p]),Addtag(t,p<<1|1,tag[t][p]),tag[t][p]=0;
}
int Ask(int tp,int L,int R,int l=0,int r=n+1,int p=1){
    if (L==l && r==R) return MIN[tp][p];
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Ask(tp,L,R,l,mid,p<<1); else if (L>mid) return Ask(tp,L,R,mid+1,r,p<<1|1);
    else return min(Ask(tp,L,mid,l,mid,p<<1),Ask(tp,mid+1,R,mid+1,r,p<<1|1));
}
void Update(int tp,int pos,int k,int l=0,int r=n+1,int p=1){
    if (l==r) {MIN[tp][p]=min(MIN[tp][p],k);return;}
    int mid=l+(r-l>>1);Pushdown(p);
    pos<=mid?Update(tp,pos,k,l,mid,p<<1):Update(tp,pos,k,mid+1,r,p<<1|1);
    Pushup(p);
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    Build(0,n+1);
    for (int i=1,A,B;i<=n;i++){
        A=min(Ask(0,0,a[i]-1),Ask(0,a[i]+1,n+1))+1;
        A=min(A,Ask(0,a[i],a[i]));
        B=min(Ask(1,0,a[i]-1),Ask(1,a[i]+1,n+1))+1;
        B=min(B,Ask(1,a[i],a[i]));
        if (a[i-1]!=a[i]) Addtag(0,1,1),Addtag(1,1,1);
        Update(0,a[i-1],B);Update(1,a[i-1],A);
    }
    printf("%d\n",min(Ask(0,0,n+1),Ask(1,0,n+1)));return 0;
}