LGP3694 邦邦的大合唱站队 学习笔记
\(\texttt{Luogu Link}\)
前言
状压热身题。\(\texttt{Warm up!}\)
另外,你知道吗,设定上,邦邦已经火了……
题意简述
\(n\) 个偶像排成一列,他们来自 \(m\) 个不同的乐队。每个团队至少有一个偶像。现在要求重新安排队列,使来自同一乐队的偶像连续的站在一起。重新安排的办法是,让若干偶像出列(剩下的偶像不动),然后让出列的偶像一个个归队到原来的空位,归队的位置任意。问最少让多少偶像出列?
形式化题意:有长为 \(n\) 的序列 \(A\),值域 \([1,m]\)。保证 \([1,m]\) 的值全部出现过。可以这样调整:选取若干个下标,将它们上的元素重新排列。要求调整后每种取值的元素形成 \(1\) 个连续段。问至少选取多少个下标?
\(n\le 10^5\),\(m\le 20\)。
做法解析
这是贪心还是 \(\texttt{DP}\)?感觉无论怎么样它进行操作时中间的的状态都好多啊……
“有若干颜色的若干元素,要交换位置或者干什么别的,中间换来换去一通”似乎很复杂,但这时候我们通常就要考虑:直接思考它的终态,对于所有颜色一种一种地把它的贡献作用到终态。
好巧不巧这道题就是一个如此的典例。显然最终队列的形态只有 \(2^m\) 种,而对于一个终态,我们尝试一个一个元素将其归位到它是简单的。
具体来说,我们直接状压 \(\texttt{DP}\)。我们的转移是往当前的队列末加一个颜色段。所以设 \(dp_S\) 为已经加入了 \(S\) 中所有颜色段的状态,\(len_S\) 为当前状态下队列的总长,显然没有后效性。我们增加颜色 \(i\) 时,要将 \((len_S,len_S+cnt_i]\) 这一段填满颜色 \(i\),因此除了 \(x\) 个本来就在该区间中的颜色 \(i\)(这个数目可以简单地前缀和求),其它的 \(i\) 肯定都要离开它的位置,这就是我们转移的代价。因为你整个转移中对每种颜色有且仅有一次计算代价,所以必然不重不漏。
讲完了。
代码实现
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5,MaxM=20,Inf=1e9;
int N,M,S[MaxN][MaxM],X,dp[1<<MaxM],len[1<<MaxM],alf;
int main(){readis(N,M);alf=(1<<M)-1;for(int i=1;i<=N;i++){for(int j=0;j<M;j++)S[i][j]=S[i-1][j];readi(X),X--,S[i][X]++;}fill(dp,dp+(1<<M),Inf),dp[0]=0;for(int s=0,t;s<=alf;s++){for(int j=0;j<M;j++){if((s>>j)&1)continue;t=s|(1<<j),len[t]=len[s]+S[N][j];minner(dp[t],dp[s]+(S[N][j]-(S[len[t]][j]-S[len[s]][j])));}}writi(dp[alf]);return 0;
}