CF1479B2 Painting the Array II 题解 [DP+线段树] Painting the Array II

Description:

​ Homer likes arrays a lot. Today he is painting an array (a_1, a_2, dots, a_n) with two kinds of colors, white and black. A painting assignment for (a_1, a_2, dots, a_n) is described by an array (b_1, b_2, dots, b_n) that (b_i) indicates the color of (a_i) ((0) for white and (1) for black).

According to a painting assignment (b_1, b_2, dots, b_n), 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 (c_1, c_2, dots, c_k), denoted (mathit{seg}(c)), 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. (mathit{seg}(a^{(0)})+mathit{seg}(a^{(1)})), is as small as possible. Find this number.

中文题面：

​ 给你一个长度为 (n) 的数列 (a) ,让你将它划分为两个子序列。分别将两个子序列中的连续的相同元素合并为一个元素，每个子序列的价值为合并后的序列长度。请你最小化两个子序列的价值之和，输出这个最小价值。

Input:

​ The first line contains an integer (n) ((1 leq n leq 10^5)).

​ The second line contains (n) integers (a_1, a_2, dots, a_n) ((1 leq a_i leq n)).

Output:

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

Sample Input 1:

6
1 2 3 1 2 2

Sample Output 1:

4

Sample Input 2:

7
1 2 1 2 1 2 1

Sample Output 2:

2

Note:

​ In the first example, we can choose (a^{(0)} = [1,1,2,2], a^{(1)} = [2,3]) and (mathit{seg}(a^{(0)}) = mathit{seg}(a^{(1)}) = 2). So the answer is (2+2 = 4).

​ In the second example, we can choose (a^{(0)} = [1,1,1,1], a^{(1)} = [2,2,2]) and (mathit{seg}(a^{(0)}) = mathit{seg}(a^{(1)}) = 1). So the answer is (1+1 = 2).

Hint:

​ 对于(100\%)的数据，(1 leq n leq 10^5,1 leq a_i leq n)

​ 时间限制： (2s)

​ 空间限制： (512M)

题目分析：

​ 看到题目的第一眼想的是贪心，但是搞不出最优策略，于是转而选择DP。

​ 当然首先将 (a) 中连续的相同元素合并成一个元素方便考虑。

​ 设(f_{i,j})表示当前一个序列以编号 (i) 来结尾，另一个序列以数字 (j) 来结尾(即 (exists k，st.1 leq k < i，a_k=j))

​ 那么有以下两种转移方式：

​ 1.(f_{i,a_{i-1}}={underset {1 leq j leq n}{operatorname {min} }} {f_{i-1,j} + (a_i eq j)})

​ 2.(f_{i,j} = f_{i-1,j} + 1)

​ 经观察，我们发现这就是个全局加，单点修改，全局查询，因此可以用线段树维护即可。

​ PS:其实可以不用线段树。。。随便搞个堆处理一下就行了。

​ 代码如下(马蜂很丑，不喜勿喷)——

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,tot,a[maxn],f[maxn<<2],tag[maxn<<2];
inline void pushdown(int now){
	tag[now<<1]+=tag[now],tag[now<<1|1]+=tag[now];
	f[now<<1]+=tag[now],f[now<<1|1]+=tag[now];tag[now]=0;
}
inline void pushup(int now){f[now]=min(f[now<<1],f[now<<1|1]);}
inline void modify(int now,int l,int r,int x,int v){
	if(l==r){f[now]+=v;return;}pushdown(now);int mid=l+r>>1;
	if(mid>=x) modify(now<<1,l,mid,x,v);else modify(now<<1|1,mid+1,r,x,v);pushup(now);
}
inline void updata(int now,int l,int r,int x,int v){
	if(l==r){f[now]=v;return;}pushdown(now);int mid=l+r>>1;
	if(mid>=x) updata(now<<1,l,mid,x,v);else updata(now<<1|1,mid+1,r,x,v);pushup(now);
}
inline void build(int now,int l,int r){
	if(l==r){if(l) f[now]=maxn;return;}int mid=l+r>>1;
	build(now<<1,l,mid),build(now<<1|1,mid+1,r),pushup(now);
}
inline int read(){
	int ret=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();return ret*f;
}
int main(){
	n=read();build(1,0,n);for(register int i=1;i<=n;i++){a[i]=read();if(a[i]!=a[i-1]) a[++tot]=a[i];}for(register int i=1;i<=tot;i++)
	{modify(1,0,n,a[i],-1);int x=f[1]+1;modify(1,0,n,a[i],1),tag[1]++,f[1]++,updata(1,0,n,a[i-1],x);}cout<<f[1]<<'
';
	return 0;
}