- 给定一个长度为(n)的数组，每个位置上有一个颜色。
- 你需要把它划分成两个子序列，求这两个子序列中颜色段数之和的最小值。
- (nle10^5)
动态规划
考虑分配完第(i)个元素之后，两个子序列中一个末尾肯定是(a_i)，而另一个末尾我们不妨假设为(j)。
于是设(f_{i,j})表示分配完第(i)个元素，另一个子序列末尾是(j)时，之前颜色段数之和的最小值。
转移分两种：
- (a_i)放在(a_{i-1})后面，则(f_{i,j}=f_{i-1,j}+[a_{i} ot=a_{i-1}])。
- (a_i)放在(j)后面，则(f_{i,a_{i-1}}=f_{i-1,j}+[a_i ot=j])。
于是这样就能得到一个(O(n^2))的暴力(DP)。
简单的优化
如果数据结构学傻的话看到这种式子可能直接就上线段树了。。。（当然也不是不可以）
然而我们发现，第一种转移实际上是全局修改，第二种转移其实可以拆成全局询问最小值和对(f_{i-1,a_i})的单点询问、对(f_{i,a_{i-1}})的单点修改。
全局修改直接记录一个全局(tag)就可以了。由于除去(tag)之后所有元素都只会越来越小，因此全局询问只需要维护一个全局最小值
代码：(O(n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
using namespace std;
int n,a[N+5],f[N+5];
int main()
{
RI i;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%d",a+i),f[i]=1e9;//初始化
RI t,tg=0,Mn=0;for(i=1;i<=n;++i) t=min(Mn+tg+1,f[a[i]]+tg),//t记录第二种转移值
a[i-1]^a[i]&&++tg,f[a[i-1]]+tg>t&&(Mn=min(Mn,f[a[i-1]]=t-tg));//tg记录第一种转移的全局标记，Mn记录全局最小值
return printf("%d
",Mn+tg),0;//答案就是最小值+全局标记
}