CF1479B2 Painting the Array II 做题记录

给定一个数组 $a$, 你将将 $a_i$ 染为 $b_i$ 色, 其中 $b$ 是由你指定的一个 01 数组. 将 $a$ 数组中被染成 0 色的数字取出来并依在 $a$ 中出现的顺序排列, 组成数组 $a^{(0)}$. 同理, 将 $a$ 数组中被染成 1 色的数字取出来并依在 $a$ 中出现的顺序排列, 组成数组 $a^{(1)}$. 我们定义 $seg(c)$ 是一个正整数, 其中 $c$ 是一个数组, $seg(c)$ 的值为在我们将 $c$ 中相邻的所有相同元素合并后, $c$ 数组的大小. 例如, $seg([1, 1, 4, 5, 1, 4]) = |[1, 4, 5, 1, 4]|=5$. 最小化 $seg(a^{(0)})+seg(a^{(1)})$。
$1\leq n\leq 10^5$，$1\le a_i\le n$。

DP

先合并序列中相邻的相同元素，即让 $a$ 中相邻两项不同，显然这样并不会改变答案。

设 $dp_{i}$ 表示前 $i$ 个分完组的答案，不难发现 $i$ 和 $i-1$ 分到同一组一定是不优的，所以 $dp_i$ 实际上的定义是前 $i$ 个分完组，$i$ 和 $i-1$ 不在同一组的答案，那么可以通过枚举 $i$ 分到的组中它前面的那个元素的位置 $j-1$ 来转移：

$dp_{i}=\min\limits_{j=1}^{i-1} dp_j+(i-j-1)+[a_{j-1}\not=a_i]$

初始状态 $dp_1=1$。

转移中加上 $i-j-1$ 是因为 $[j,i-1]$ 都要分配到一组里，但是 $j$ 的贡献已经包含在了 $dp_j$ 里面。

不难发现，由于 $[j,i-1]$ 都要分配到一组里，所以 $j$ 肯定越大越好，那么 $j$ 就只能取 $a_i$ 在 $i$ 之前最后的出现位置的后一个位置 $lst_{a_i}+1$ 或者 $i-1$。

所以有转移：

$dp_{i}=\min(dp_{lst_{a_i}+1}+(i-lst_{a_i}-2),dp_{i-1}+[a_{i-2}\not=a_{i}])$

贪心

其实这就是 Bélády's algorithm，贪心策略如下：

1. 建立两个数组 $c_0$ 和 $c_1$ 用来存储两组具体的数值，初始两个数组均为空，记 $d_0,d_1$ 分别表示两个数组的末尾元素；
2. 预处理出 $nxt_{i,j}$ 表示 $i$ 后面第一个出现的 $j$ 的位置；
3. 从前往后扫描 $a$，扫描到 $a_i$ 的时候：
   1. 若 $c_0$ 非空且 $a_i=d_0$，那么把 $a_i$ 放到 $c_0$ 末尾；
   2. 否则若 $c_1$ 非空且 $a_i=d_1$，那么把 $a_i$ 放到 $c_1$ 末尾；
   3. 否则若 $c_0$ 和 $c_1$ 有一个为空，那么把 $a_i$ 放入空的那个数组；
   4. 否则若 $nxt_{i,d_0}>nxt_{i,d_1}$，那么把 $a_i$ 放到 $c_0$ 末尾；
   5. 否则把 $a_i$ 放到 $c_1$ 末尾；
4. 最后扫一遍 $c_0,c_1$ 即可求出答案；

理性证明在官方题解中有提及，这里给出感性证明：

首先步骤 $1$、$2$ 和 $4$ 都很显然，重点证明步骤 $3$，第 $1$、$2$、$3$ 条都很显然，重点证明第 $4$ 条和第 $5$ 条。

$nxt_{i,d_0}>nxt_{i,d_1}$ 表明 $d_0$ 和与它相等的元素相遇需要把更多元素放进 $c_1$，让 $d_0$ 等它后面相同的元素就不是很优，所以要把 $a_i$ 放入 $c_0$，第 $5$ 条同理。

感性证明完毕。

参考代码：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=100005;

int n,a[S];

namespace dp
{
	int m,b[S];
	int lst[S],dp[S];
	inline void slove()
	{
		for(int i=1;i<=n;i++) if(a[i]!=a[i-1]) b[++m]=a[i];
		dp[1]=1;
		lst[b[1]]=1;
		for(int i=2;i<=m;i++)
		{
			dp[i]=dp[i-1]+(b[i]!=b[i-2]);
			if(lst[b[i]]!=0)
			{
				int j=lst[b[i]]+1;
				dp[i]=min(dp[i],dp[j]+(i-j-1));
			}
			lst[b[i]]=i;
		}
		printf("%d\n",dp[m]);
	}
}

namespace greedy
{
	vector<int> pos[S];
	int tb,b[S];
	int tc,c[S];
	inline void slove()
	{
		for(int i=1;i<=n;i++) pos[a[i]].push_back(i);
		for(int i=1;i<=n;i++) pos[i].push_back(n+1);
		for(int i=1;i<=n;i++)
		{
			if(a[i]==b[tb]||tb==0) b[++tb]=a[i];
			else if(a[i]==c[tc]||tc==0) c[++tc]=a[i];
			else if(pos[b[tb]]>pos[c[tc]]) b[++tb]=a[i];
			else c[++tc]=a[i];
			pos[a[i]].erase(pos[a[i]].begin());
		}
		int ans=0;
		for(int i=1;i<=tb;i++) ans+=b[i]!=b[i-1];
		for(int i=1;i<=tc;i++) ans+=c[i]!=c[i-1];
		printf("%d\n",ans);
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
//	dp::slove();
//	greedy::slove();
	return 0;
}