当前位置: 首页 > news >正文

LGP3694 邦邦的大合唱站队 学习笔记

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;
}
http://www.hskmm.com/?act=detail&tid=36852

相关文章:

  • 2025.10.22学习记录
  • 衡量效率,质量,运维的效率指标
  • LeeCode_101对称二叉树
  • TRAE 设计团队如何玩转 Vibe Coding(上)|高美感页面生成篇
  • LeeCode_226反转二叉树
  • 2025多校冲刺CSP模拟赛7 总结
  • 详细介绍:wpf之 Popup
  • 结对项目-生成四则运算
  • ? #4
  • CSS3 超实用属性:pointer-events (可穿透图层的鼠标事件)
  • 类和对象
  • 取证-windbg和dmp,以及文件分析基本流程
  • 【比赛记录】2025CSP+NOIP 冲刺模拟赛合集Ⅱ
  • 羊驼二次免疫的六大风险:纳米抗体制备不可忽视的 “隐形陷阱”
  • 完整教程:C++项目:仿muduo库高并发服务器-------connection模块
  • 深入解析:线性代数 SVD | 令人困扰的精度 1
  • 营销数字化专家要求
  • 小程序反编译包的架构文件
  • 10.22 CSP-S模拟37/2025多校冲刺CSP模拟赛7 改题记录
  • [题解]P11126 [ROIR 2024] 三等分的数组 (Day 2)
  • Acrobat Pro DC 2025下载及破解安装教程,附永久免费免激活中文版Acrobat Pro DC安装包(稳定版)
  • VSLAM 十四讲--阅读中知识点记录
  • 数据库学习篇(持续更新中)
  • Fortinet产品安全漏洞分析:FGFM协议未经认证连接重置漏洞
  • 李超线段树
  • fiddler修改请求(修改搜索框的内容)
  • 20251022
  • 10月22号
  • 将“百度”的URL改为“163网易云”(修改URL地址)
  • Yolo11分割模型