题外话

心碎的一场，一开始40分钟秒掉三题，结果后来fst掉两题（一题是忘了赋INF，另一题是>0写成>=0，这次pretest数据真的比以往弱太多！），掉了一百二十分差点下蓝，一朝回到解放前，心态都崩了。哭哭，近期都没心情打了

题目地址

https://codeforces.com/contest/1480/problem/D1

题目大意

给一个长n的序列，可以按顺序分成两组（要保留先后顺序的），求怎么样使两个序列的段数和最大？

说明：连续的同种数字算同一段，比如$[1,2,3]$有3段，$[1,1,2,2,3,3,3,3]$同样也是3段。

解法

分析

我一开始也想到了用贪心，但是其实可以发现这题有很多需要讨论的地方。

首先，当前数字放在特定的一组中，可以隔开之后来的数字使得段数增加，比如对序列$[1,2,3,2,2]$

当前$A:[1]$和$B:[2]$，下一个来的为$3$。这个$3$一定要放在第二组才能使结果最大化即$A:[1,2]$和$B:[2,3,2]$

这里的重点在于：之后出现了连续的一段$[2,2]$对于连续的一段我们没得选,如果A或者B的尾部同样也有2，那么就会使答案损失1。

因此，如果现在有一个数字要选择插入A还是B，我们需要依据A和B尾端的数字以及之后“连着的两个相同数字”进行讨论

解

预处理一个nxt数组,表示离当前位置i最近的**“连续两个相同数字”**是什么。

如果两个序列其中一个的尾部和a[i]相同，那么肯定是要放到另一个序列中去的。
如果两个序列的尾部都不同于当前a[i]，那么就要依据nxt[i]和两个尾部进行讨论，如果序列A的尾部和nxt[i]相同，那么就放在序列A上，反之则放在B上。

代码

有些细节上还需要讨论以下，比如a中一段长段的末尾和单个数字是一样讨论的等等。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f

int n;
const int MAXN = 114514;
int a[MAXN],nxt[MAXN];

void solve(){
    cin>>n;
    rep(i,1,n) cin>>a[i];
    nxt[n]=-1;//记录之后最近一次出现两次以上的数字
    repb(i,n-1,1){
        if(a[i]==a[i+1]) nxt[i]=a[i];
        else nxt[i]=nxt[i+1];
    }
    int top[2];//两个栈的栈顶元素
    top[0]=top[1]=-1;
    int res=0;
    rep(i,1,n){
        if(a[i]==a[i+1]){//重复长段,放哪儿都一样
            if(top[0]!=a[i]) res++;
            top[0]=a[i];
        }
        else{//重复长段末尾或单个字符
            if(top[0]==a[i]) res+=(top[1]!=a[i]),top[1]=a[i];
            else if(top[1]==a[i]) res+=(top[0]!=a[i]),top[0]=a[i];
            else{
                if(top[0]==nxt[i]) res++,top[0]=a[i];
                else res++,top[1]=a[i];
            }
        }
    }
    cout<<res<<endl;
}

int main(){
    solve();
}