P6622 [省选联考 2020 A/B 卷] 信号传递
题目大意详细题目传送门
给出 \(n,m,k\) 和一个长度为 \(n\) 的序列 \(S\)，其中 \(S_i\in \)。
对于一个 \(x\rightarrow y\) 的代价 \(f(x,y)\)，有：
\[ \left\{\begin{aligned}y-x &&x\leq y\\kx+ky &&x>y\\\end{aligned}\right.\]
你需要求一个长度为 \(m\) 排列 \(P\),使 \(\sum_{i=1}^{n-1}f(P_{S_i},P_{S_i+1})\) 最小。
\(n\leq 10^5,m\leq 23,k\leq 100\)
思路
发现 \(m\) 很小，所以看起来就很像一些状压动归。但是发现即使是枚举 \(P\) 的暴力要求一个总代价也是 \(O(n\cdot m!)\) 的，所以希望将它转成一个只关于 \(m\) 的形式。
这个时候可以拆贡献，发现对于 \(S_i\) 的贡献只与 \(S_i+1\) 有关。这个时候我们可以记 \(C(x,y)\) 表示 \(S\) 中有多少 \((S_i=x,S_{i+1}=y)\)。这样我们在算 \(P\) 的代价时就可以枚举 \(x,y\in\)，然后加贡献
\
这样就优化到了 \(O(m^2m!)\)，我们的时间复杂度已与 \(n\) 无关。
然后考虑状压动规。如果先考虑 \(F_s\) 表示现在 \(\) 的数分别填在了 \(s\) 为 \(1\) 的位置上，但是无法转移，因为不知道具体是哪些值的话 \(C(x,y)\) 就是无法更新的。
但是可以有转移 \(F_s\) 表示现在填了前 \(|s|\) 个位置，填了 \(s\) 中的这些数。发现就可以转移，因为我们只关心大小关系，那么还没有出现的肯定在之后，那么转移时的大小关系就可以确定了。
那么转移一个 \(i\) 时考虑到 \(j\) 有几种情况：
[*]若 \(i\rightarrow j\)， \(j\in s\)，\(P_jP_i\)，所以有贡献 \(C(i,j)\cdot (-P_i)\)
[*]若 \(j\rightarrow i\)， \(j\in s\)，\(P_jP_i\)，所以有贡献 \(C(j,i)\cdot kP_i\)
那么可以转移
\
\
其中按照定义 \(P_i=|s|+1\)。
那么现在的时间复杂度是 \(O(2^mm^2)\) 的，已经有 \(80\) 分了。发现能不能先预处理出 \(G(s,i)\)。发现 \(G(s,i)\) 可以从任何一个大小为 \(|s|-1\) 的子集转移过来。那么可以不妨从去掉最低位 \(1\)（即 lowbit，不妨设位置为 \(j\)） 的位置 \(s^{'}\) 转移。
\
\[=G(s^{'},i)+C(i,j)\cdot (k+1)+C(j,i)\cdot (1-k)\]
现在我们已经做到了时空都是 \(O(2^mm)\) 了，但是发现空间不够大。但是发现所有的 \(G(s,i),i\in s\) 都是没有意义的，所以我们可以只保存 \(2^{m-1}\) 个 \(G\)，虽然实现麻烦但是可以优化到空间 \(O(2^{m-1}m)\),时间 \(O(2^mm)\) 可以通过本题。
代码
#include#define endl '\n'#define rep(i,a,b) for(register ll i=(a);i 鼓励转贴优秀软件安全工具和文档！ 感谢分享，学习下。 过来提前占个楼 喜欢鼓捣这些软件，现在用得少，谢谢分享！ yyds。多谢分享 东西不错很实用谢谢分享 感谢分享 过来提前占个楼 谢谢分享，辛苦了 谢谢分享，辛苦了 用心讨论，共获提升！ 这个有用。 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 东西不错很实用谢谢分享 分享、互助 让互联网精神温暖你我 这个好，看起来很实用 东西不错很实用谢谢分享 东西不错很实用谢谢分享 懂技术并乐意极积无私分享的人越来越少。珍惜
页:
[1]
2