Codeforces Round #700 (Div. 2) D1. Painting the Array I（暴力+后缀）_round 700

 有 n 个数，可以将他们分成 2 组，但是相对顺序不可以被打乱，在每一组中相邻的多个相同的元素 a，必须合成为一个元素 a，问如何构造这两组，使得元素数量最多

题目翻译的可能不够清楚，建议读懂原题。

感觉这应该是一道 dp 的题目，但是却没有用 dp 来解

如样例 1 所示，预处理得  1(2) 2(2) 3(3) 其中括号内为元素的数量，括号前为元素的大小

这样很明显两组分别为 1 2 3 和 1 2 3，多余的 3 无论放到哪一组中都会被合成，这样算法就很好实现了

但是需要注意，给出数据  1 1 2 3 2 2，最优解应为 1 2 3 2 和 1 2 ，背标红的 2 前面应该有 3 来分割才能达到最优，所以要判断当有单个元素出现时，应该放到那一组里

所以在预处理出 d 数组 ，d[i] 表示后面开始离 i 位置最近的数量>=2 的元素是什么

const int N=1e6+5;
 
    int n,m,t;
    int i,j,k;
    int a[N];
    vector<pii> v;
    int d[N];
 
int main()
{
    //IOS;
    while(~sd(n)){
        for(int i=1;i<=n;i++) sd(a[i]);
        int res=1;
        for(int i=2;i<=n+1;i++){
            if(a[i]!=a[i-1]) v.pb(mp(a[i-1],res)),res=1;
            else res++;
        }
        int len=v.size(),ans=0;
        for(int i=len-2;i>=0;i--){
            if(v[i+1].sc>=2) d[i]=v[i+1].fr;
            else d[i]=d[i+1];
        }
        int uu=-1,vv=-1;
        for(int i=0;i<len;i++){
            int x=v[i].sc;
            int y=v[i].fr;
            if(x>=2){
                if(uu!=y && vv!=y) ans+=2,uu=vv=y;
                else if(uu!=y || vv!=y) ans++,uu=vv=y;
            }
            else if(x==1){
                if(uu==y && vv==y) continue;
                int flag=1;
                if(uu!=y && vv!=y && i!=len-1){
                    int tmp=d[i];
                    if(tmp==vv) vv=y,ans++,flag=0;
                    else if(tmp==uu) uu=y,ans++,flag=0;
                }
                if(!flag) continue;
                if(uu!=y) ans++,uu=y;
                else if(vv!=y) ans++,vv=y;
            }
        }
        pd(ans);
    }
    //PAUSE;
}