CF1479B2 Painting the Array II 做题记录

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

DP

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

dpidp_{i} 表示前 ii 个分完组的答案,不难发现 iii1i-1 分到同一组一定是不优的,所以 dpidp_i 实际上的定义是前 ii 个分完组,iii1i-1 不在同一组的答案,那么可以通过枚举 ii 分到的组中它前面的那个元素的位置 j1j-1 来转移:

dpi=minj=1i1dpj+(ij1)+[aj1=ai]dp_{i}=\min\limits_{j=1}^{i-1} dp_j+(i-j-1)+[a_{j-1}\not=a_i]

初始状态 dp1=1dp_1=1

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

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

所以有转移:

dpi=min(dplstai+1+(ilstai2),dpi1+[ai2=ai])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. 建立两个数组 c0c_0c1c_1 用来存储两组具体的数值,初始两个数组均为空,记 d0,d1d_0,d_1 分别表示两个数组的末尾元素;
  2. 预处理出 nxti,jnxt_{i,j} 表示 ii 后面第一个出现的 jj 的位置;
  3. 从前往后扫描 aa,扫描到 aia_i 的时候:
    1. c0c_0 非空且 ai=d0a_i=d_0,那么把 aia_i 放到 c0c_0 末尾;
    2. 否则若 c1c_1 非空且 ai=d1a_i=d_1,那么把 aia_i 放到 c1c_1 末尾;
    3. 否则若 c0c_0c1c_1 有一个为空,那么把 aia_i 放入空的那个数组;
    4. 否则若 nxti,d0>nxti,d1nxt_{i,d_0}>nxt_{i,d_1},那么把 aia_i 放到 c0c_0 末尾;
    5. 否则把 aia_i 放到 c1c_1 末尾;
  4. 最后扫一遍 c0,c1c_0,c_1 即可求出答案;

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

首先步骤 112244 都很显然,重点证明步骤 33,第 112233 条都很显然,重点证明第 44 条和第 55 条。

nxti,d0>nxti,d1nxt_{i,d_0}>nxt_{i,d_1} 表明 d0d_0 和与它相等的元素相遇需要把更多元素放进 c1c_1,让 d0d_0 等它后面相同的元素就不是很优,所以要把 aia_i 放入 c0c_0,第 55 条同理。

感性证明完毕。

参考代码:

#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;
}