题解：P17329 [ICPC 2018 Nanjing R] Lagrange the Chef
lailai0916
·
·
题解
题意简述
只有菜品 X 与 Y 不能相邻，其他菜品没有限制。
每次可以把一道菜移动到任意位置。
求把序列变为合法序列的最少操作数，或判断无解。
解题思路
把 X、Y 和其他菜品分别记为 0,1,2。
类型 2 可以隔开相邻的 0 与 1。
若原序列已经没有相邻的 0,1，答案为 0。
若原序列不合法且没有类型 2，
无论怎样排列，0 与 1 的分界处都会相邻，答案为 -1。
一次移动会改变被移动元素的位置，
所有未移动元素仍保持原相对顺序。
因此，执行若干次移动等价于保留原序列的一个子序列，
再把其他元素分别插入目标位置。
只要目标排列合法，每个未保留元素移动一次就足够。
先考虑保留的 0,1 中两种类型都出现的情况。
设保留的 0,1 子序列长度为 k，
其中相邻异类元素的对数为 j。
每对异类元素之间都需要至少一个类型 2，所以必须满足：
j\leq c_2
其中 c_t 表示类型 t 的总数。
用所有类型 2 把原序列分成若干段。
若保留子序列中的一对相邻异类元素来自不同段，
它们之间原本就有一个未移动的类型 2。
若它们来自同一段，
必须移动一个类型 2 到二者之间。
设同段异类相邻对共有 d 个。
可以保留 k 个类型 0,1，
并保留除上述 d 个以外的所有类型 2。
所需操作数为：
c_0+c_1-k+d
当 j\geq1 时，保留子序列同时包含两种类型。
移动需要分隔的 d 个类型 2 后，
合法序列中同时存在 0 邻接类型 2 和
所有未保留的 $0,1$ 都能插入对应同类的一侧，
不会产生新的异类相邻，因此上式不仅是下界，也能够达到。
于是只需在 $1\leq j\leq c_2$ 时最大化 $k-d$。
从左到右扫描原序列。
设 $f_{t,j,q}$ 表示当前保留子序列非空，
末尾类型为 $t$，包含 $j$ 对异类相邻，
且 $k-d$ 的最大值。
$q=1$ 表示末尾元素位于当前类型 $2$ 之后的这一段，
$q=0$ 表示末尾元素位于更早的段。
每遇到一个类型 $2$，就把所有 $q=1$ 的状态转成 $q=0$。
扫描到类型 $v\in\{0,1\}$ 时，可以不保留它。
若保留它，分以下情况：
- 以它开始子序列，得到 $j=0$、$k-d=1$；
- 前一个保留元素也是 $v$，只有 $k$ 增加一，状态值增加一；
- 前一个元素异类且 $q=1$，$k,d,j$ 都增加一，状态值不变；
- 前一个元素异类且 $q=0$，$k,j$ 增加一，状态值增加一。
每次用新数组承接转移，原状态自然对应不保留当前元素。
扫描结束后，在 $1\leq j\leq c_2$ 的状态中取最大的 $k-d$。
还要单独处理只保留一种类型的方案。
以保留所有 $0$ 为例，所有 $1$ 都需要移动。
若存在一个不含 $0$ 的分段，
可以把全部 $1$ 连续插入该段，答案为 $c_1$。
否则每个分段中都有未移动的 $0$。
需要额外移动一个类型 $2$ 到序列端点，
再把全部 $1$ 放到这个类型 $2$ 的外侧，答案为 $c_1+1$。
只保留 $1$ 时完全对称。
三类方案取最小值。
状态数为 $O(n^2)$，每个元素对所有状态作常数次转移，
时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=5005;
const int inf=0x3f3f3f3f;
int a[N],cnt[3];
int f[2][N][2];
int g[2][N][2];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,x,y;
cin>>n>>x>>y;
bool bad=0;
for(int i=1;i<=n;i++)
{
int v;
cin>>v;
if(v==x)a[i]=0;
else if(v==y)a[i]=1;
else a[i]=2;
cnt[a[i]]++;
if(i>1&&a[i]+a[i-1]==1)bad=1;
}
if(!bad)
{
cout<<0<<'\n';
return 0;
}
if(cnt[2]==0)
{
cout<<-1<<'\n';
return 0;
}
bool gap[2]={};
bool vis[2]={};
for(int i=1;i<=n+1;i++)
{
if(i==n+1||a[i]==2)
{
for(int j=0;j<2;j++)
{
if(!vis[j])gap[j]=1;
vis[j]=0;
}
}
else vis[a[i]]=1;
}
for(int i=0;i<2;i++)
{
for(int j=0;j<=cnt[2];j++)
{
for(int k=0;k<2;k++)f[i][j][k]=-inf;
}
}
for(int i=1;i<=n;i++)
{
if(a[i]==2)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<=cnt[2];k++)
{
f[j][k][0]=max(f[j][k][0],f[j][k][1]);
f[j][k][1]=-inf;
}
}
continue;
}
memcpy(g,f,sizeof f);
int v=a[i];
g[v][0][1]=max(g[v][0][1],1);
for(int j=0;j<2;j++)
{
for(int k=0;k<=cnt[2];k++)
{
if(j==v)
{
if(f[j][k][0]>=0)g[v][k][1]=max(g[v][k][1],f[j][k][0]+1);
if(f[j][k][1]>=0)g[v][k][1]=max(g[v][k][1],f[j][k][1]+1);
}
else if(k<cnt[2])
{
if(f[j][k][0]>=0)g[v][k+1][1]=max(g[v][k+1][1],f[j][k][0]+1);
if(f[j][k][1]>=0)g[v][k+1][1]=max(g[v][k+1][1],f[j][k][1]);
}
}
}
memcpy(f,g,sizeof g);
}
int ans=min(cnt[1]+!gap[0],cnt[0]+!gap[1]);
int mx=-inf;
for(int i=0;i<2;i++)
{
for(int j=1;j<=cnt[2];j++)
{
mx=max(mx,f[i][j][0]);
mx=max(mx,f[i][j][1]);
}
}
if(mx>=0)ans=min(ans,cnt[0]+cnt[1]-mx);
cout<<ans<<'\n';
return 0;
}
```