给定一个数组 , 你将将 染为 色, 其中 是由你指定的一个 01 数组. 将 数组中被染成 0 色的数字取出来并依在 中出现的顺序排列, 组成数组 . 同理, 将 数组中被染成 1 色的数字取出来并依在 中出现的顺序排列, 组成数组 . 我们定义 是一个正整数, 其中 是一个数组, 的值为在我们将 中相邻的所有相同元素合并后, 数组的大小. 例如, . 最小化 。
,。
DP
先合并序列中相邻的相同元素,即让 中相邻两项不同,显然这样并不会改变答案。
设 表示前 个分完组的答案,不难发现 和 分到同一组一定是不优的,所以 实际上的定义是前 个分完组, 和 不在同一组的答案,那么可以通过枚举 分到的组中它前面的那个元素的位置 来转移:
初始状态 。
转移中加上 是因为 都要分配到一组里,但是 的贡献已经包含在了 里面。
不难发现,由于 都要分配到一组里,所以 肯定越大越好,那么 就只能取 在 之前最后的出现位置的后一个位置 或者 。
所以有转移:
贪心
其实这就是 Bélády's algorithm
,贪心策略如下:
- 建立两个数组 和 用来存储两组具体的数值,初始两个数组均为空,记 分别表示两个数组的末尾元素;
- 预处理出 表示 后面第一个出现的 的位置;
- 从前往后扫描 ,扫描到 的时候:
- 若 非空且 ,那么把 放到 末尾;
- 否则若 非空且 ,那么把 放到 末尾;
- 否则若 和 有一个为空,那么把 放入空的那个数组;
- 否则若 ,那么把 放到 末尾;
- 否则把 放到 末尾;
- 最后扫一遍 即可求出答案;
理性证明在官方题解中有提及,这里给出感性证明:
首先步骤 、 和 都很显然,重点证明步骤 ,第 、、 条都很显然,重点证明第 条和第 条。
表明 和与它相等的元素相遇需要把更多元素放进 ,让 等它后面相同的元素就不是很优,所以要把 放入 ,第 条同理。
感性证明完毕。
参考代码:
#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;
}