传送门
做法一：首先将给定数组重复的数删掉。对于最近的两个相同的数，令其位置为\([l,r]\)，看作是覆盖区间\([l,r]\)的一条线段。那么对于当前数组的若干条线段，若保留该线段，则代表这两个数涂相同颜色且在该颜色下相邻。发现若一个线段完全包含另一条线段，则一定选小的线段更优。对于两条不完全包含但是有重复区间的线段\([l_{1},r_{1}]\)和\([l_{2},r_{2}]\)，令\(l_{1} \leq l_{2}\),若\(l_{2} < r_{1}-1\)，则\(l_{2}+1,r_{1}-1\)之间一定有别的数，会导致其中一条线段无法被选择，故此时选择左端点更小的更优。
做法二：同样首先将给定数组重复的数删掉。若用DP解决，显然不能令\(dp_{i，0/1}\)表示第\(i\)个数涂黑/白的最小答案，因为这样会导致状态难以转移。令\(dp_{i}\)表示\(i\)这个位置作为颜色分界点的最小答案，即\(b_{i} ≠ b_{i-1}\)，此时转移变得简单：
\(dp_{i}=min(dp_{j}+(i-j-1)+[a_{j-1}≠a_{i}])\)
暴力转移是不对的。化简一下式子：发现\(i\)是常量，将其移到左边：
\(dp_{i}-i=min(dp_{j}-j-1+[a_{j-1}≠a_{i}])\)
貌似只需要维护\(dp_{i}-i\)这个值，然后就可以直接转移过来了，但是还有\([a_{j-1}≠a_{i}]\)这个东西。可以用一个桶来储存，\(vt_{i}\)表示\(a_{j-1}=i\)时最小的\(dp_{j}-j\)，这样貌似能够通过维护查询区间最小值来转移，但是还能优化为\(O(n)\)
假定当前\(a_{i}\)第一次出现，则有\(dp_{i}-i=dp_{i-1}-(i-1)\)，即\(dp_{i-1}-(i-1)\)已经代表了在没有数与\(a_{i}\)相同的情况下的\(min(dp_{j}-j-1+[a_{j-1}≠a_{i}])\)
而若存在与当前数相同，则利用前面维护的桶再取个最小值即可。
//Codeforces Round 700 (Div. 1)_B2. Painting the Array II
#include<bits/stdc++.h>
#define int long longusing namespace std;const int N = 5e5 + 10;
const int inf = 1e18;
int n,a[N];void solve() {cin >> n;for(int i = 1;i <= n;i++) cin >> a[i];int nn = unique(a + 1,a + 1 + n) - a - 1;vector<int> vt(n + 10,inf);vector<int> dp(n + 10);for(int i = 1;i <= nn;i++) {dp[i] = i + (dp[i - 1] - (i - 1));dp[i] = min(dp[i],vt[a[i]] + i - 1);vt[a[i - 1]] = min(vt[a[i - 1]],dp[i] - i);}int ans = inf;for(int i = 1;i <= nn;i++) ans = min(ans,dp[i] + nn - i);cout << ans << '\n';
}signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;while(t--) solve();return 0;
}