#700 (Div. 2)D1. Painting the Array I（贪心）_the only difference between the two versions is th

题目描述

The only difference between the two versions is that this version asks the maximal possible answer.
Homer likes arrays a lot. Today he is painting an array a1,a2,…,an with two kinds of colors, white and black. A painting assignment for a1,a2,…,an is described by an array b1,b2,…,bn that bi indicates the color of ai (0 for white and 1 for black).
According to a painting assignment b1,b2,…,bn, the array a is split into two new arrays a(0) and a(1), where a(0) is the sub-sequence of all white elements in a and a(1) is the sub-sequence of all black elements in a. For example, if a=[1,2,3,4,5,6] and b=[0,1,0,1,0,0], then a(0)=[1,3,5,6] and a(1)=[2,4].
The number of segments in an array c1,c2,…,ck, denoted seg©, is the number of elements if we merge all adjacent elements with the same value in c. For example, the number of segments in [1,1,2,2,3,3,3,2] is 4, because the array will become [1,2,3,2] after merging adjacent elements with the same value. Especially, the number of segments in an empty array is 0.
Homer wants to find a painting assignment b, according to which the number of segments in both a(0) and a(1), i.e. seg(a(0))+seg(a(1)), is as large as possible. Find this number.

Input

The first line contains an integer n (1≤n≤105).
The second line contains n integers a1,a2,…,an (1≤ai≤n).

Output

Output a single integer, indicating the maximal possible total number of segments.

Examples

input
7
1 1 2 2 3 3 3
output
6
input
7
1 2 3 4 5 6 7
output
7

Note

In the first example, we can choose a(0)=[1,2,3,3], a(1)=[1,2,3] and seg(a(0))=seg(a(1))=3. So the answer is 3+3=6.
In the second example, we can choose a(0)=[1,2,3,4,5,6,7] and a(1) is empty. We can see that seg(a(0))=7 and seg(a(1))=0. So the answer is 7+0=7.

题目大意

给出一个序列a[]，将a[]分成两个子数组a1和a2。并使得seg(a1)+seg(a2)最大。
seg(a)为a中连续段的个数。例如：a[1,1,2,2,3,3,3,2]中的连续段有[1,2,3,2]四个，seg(a)=4。

题目分析

考虑如何才能使得答案尽可能的大，这里我们可以采用贪心的方法来完成。
我们来按顺序将a中的所有元素放入a1和a2中。
设：p为当前a1中的最后一个元素的值，q为当前a2中的最后一个元素的值

1. 当p==q时，将a[i]放在哪里都可以，放入不同的数组中不会对最终结果产生影响。
2. p==a[i]&&q!=a[i]，显然应该把a[i]放到a2中去。我们将a[i]放到a2中可以使得答案+1，而放到a1中则不能使答案增加。能让答案增加就尽可能的让答案增加，不会使答案变得更差。
3. p!=a[i]&&q==a[i]，同理，应该把a[i]放到a1中去。
4. p!=a[i]&&q!=a[i]，这时将a[i]放到哪里就该仔细思考了。
   我们可以求出p和q在a[i]之后出现的离i最近的位置f[p][pp]和f[q][qq]，如果f[p][pp]<f[q][qq]，那么就将a[i]放入a1中，否则放入a2中。
   这里只需要举一个简单的小例子：
   假设p=1，q=2，a中还有[3,2,2,1]这三个元素，如果将3放入a1中，那么答案只能再加3。但是如果将3放入a2中，答案可以再加4。

代码如下

法一：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <bitset>
#include <algorithm>
#define LL long long
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f;
int a[N];
vector<int> f[N];				//f[x]表示a[]中等于x的数的下标都有哪些
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[a[i]].push_back(i);
	}
	int p=0,q=0;				//即为分析中的p和q
	int ans=0;					//记录答案
	for(int i=1;i<=n;i++)
	{
		if(p==q)				//情况1
		{
			if(p!=a[i]) p=a[i],ans++;
		}
		else if(p==a[i]) q=a[i],ans++;			//情况2
		else if(q==a[i]) p=a[i],ans++;			//情况3
		else
		{										//情况4
			int pp=lower_bound(f[p].begin(),f[p].end(),i)-f[p].begin();	
			int qq=lower_bound(f[q].begin(),f[q].end(),i)-f[q].begin();
			//找出f[p]和f[q]中大于等于i的最小值，因为f中的元素是有序的（因为是有序插入的），因此可以用二分
			if(pp>=f[p].size()) q=a[i];			//pp==f[p].size()，说明a[i]后面没有p这个元素了，因此优先放入q中
			else if(qq>=f[q].size()) p=a[i];	//同理，优先放入p中
			else if(f[p][pp]>f[q][qq]) q=a[i];	//否则优先放入小的中
			else p=a[i];
			ans++;
		}
	}
	printf("%d\n",ans);
    return 0;
}
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

法二：法一的升级版，只进行了一处修改，如果能看懂法一那么法二应该可以很容易的理解。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <bitset>
#include <algorithm>
#define LL long long
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f;
int a[N],num[N];					//用num[]存储当前进行到的位置
vector<int> f[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[a[i]].push_back(i);
	}
	int p=0,q=0;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		num[a[i]]++;				//进行到a[i]，则num[a[i]]++。
		if(p==q)
		{
			if(p!=a[i]) p=a[i],ans++;
		}
		else if(p==a[i]) q=a[i],ans++;
		else if(q==a[i]) p=a[i],ans++;
		else
		{
			if(num[p]>=f[p].size()) q=a[i];				//这样pp==num[p]，qq==num[q]。
			else if(num[q]>=f[q].size()) p=a[i];
			else if(f[p][num[p]]>f[q][num[q]]) q=a[i];
			else p=a[i];
			ans++;
		}
	}
	printf("%d\n",ans);
    return 0;
}
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