Codeforces Round #700 (Div. 2) D1. Painting the Array I (贪心)_codeforces painting the array i

题意：
给出一个数组，要求将这个数组分为两个子序列。定义子序列的价值为：将连续相同的数合并为一个后，剩下数的个数。求两个子序列价值相加最大。

题解：
设x为第一个序列的最后一个元素，y为第二个序列的最后一个元素。那么可以分类讨论：
1.x==y
此时a[i]不管放哪个都没影响。
2.a[i]==x&&a[i]!=y
此时应该放y后面，为什么？假设我们放y后面，接下来的元素可能使答案+1，也可能不，答案上限可以+2，但如果放在x后面，接下来的元素虽然随便放答案都可以+1，但是上限只能+1，随意考虑放在y后面。
3.a[i]!=x&&a[i]==y
同上。
4.a[i]!=x&&a[i]!=y
那么这个时候就不能随便放了，举个例子，x=1,y=2, 元素为 3 2 2，很明显，3放在2后面才是最优的。那么设nex[i]表示 i 下次出现的位置，如果nex[x]<nex[y],说明要把a[i]放在x后面去隔断，反之放在y后面。

代码：

#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<ctime>
#define iss ios::sync_with_stdio(false)
#define DEV_RND ((int)rand()*RAND_MAX+rand())
#define RND(L,R) (DEV_RND%((R)-(L)+1)+(L))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int>pii;
const int MAXN=1e5+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
std::vector<int> v[MAXN];
int a[MAXN];
int num[MAXN];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        v[a[i]].push_back(i);
    }
    int ans=0;
    int x=0,y=0;
    for(int i=1;i<=n;i++)
    {
        num[a[i]]++;
        if(x==y)
        {
            if(x!=a[i])
            {
                ans++;
                x=a[i];
            }
        }
        else
        {
            if(a[i]==x)
            {
                ans++;
                y=a[i];
            }
            else if(a[i]==y)
            {
                ans++;
                x=a[i];
            }
            else
            {
                if(num[x]>=v[x].size())
                {
                    ans++;
                    y=a[i];
                }
                else if(num[y]>=v[y].size())
                {
                    ans++;
                    x=a[i];
                }
                else if(v[x][num[x]]<v[y][num[y]]) 
                {
                    ans++;
                    x=a[i];
                }
                else
                {
                    ans++;
                    y=a[i];
                }
            }
        }
    }
    printf("%d\n",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85