20240913 ARC104
感觉后四题价值都很高,dp 还是弱项,待加强。
A Plus Minus
水,略。
B DNA Sequence
只有对应的两种字符数量相等才能满足条件,直接 \(O(n^2)\) 枚举子串可过。用 unordered_map 开桶能做到 \(O(n)\)。
C Fair Elevator
赛时没想到 dp,乱搞做法差 1 个点就过了。
考虑 dp,设 \(f_i\) 表示前 \(i\) 个位置能否完成分配。转移时枚举一个独立的区间 \([j,i]\),判断这个区间是否可行并转移。
考虑如何判断一个独立区间是否合法。不妨设这个区间内没有独立的区间,否则可以从另一个状态转移。注意到所有的 \([a_i,b_i]\) 间不存在包含关系,所以这个独立区间内的所有区间一定两两相交。于是这个独立区间会是这样:\(\{a_{i_1},a_{i_2},...,a_{i_m},b_{i_1},b_{i_2},...,b_{i,m}\}\)。根据这个性质判断就好。
似乎可以搜,但要剪枝。
D Multiset Mean
遗憾的,赛时连第一层转化都没想到,乱七八糟想,浪费很多时间。又 get 一种多重背包优化。
先考虑对于每个平均值 \(x\) 单独求解。将每个数的价值减去 \(x\),那么问题转化为选出一些数使和为 0。显然可以多重背包求,但是 \(O(n^4k)\)。
再次转化,和为 0 也就是说正数和与负数和的绝对值相等。又注意到可选的正数和负数都是一段连续的数,于是可以预处理 \(f_{i,j}\) 表示选 \([1,i]\) 的数,每个数最多 \(k\) 个,和为 \(j\) 的方案数。这里的多重背包可以用前缀和优化,是 \(O(n^3k)\) 的。那么答案为 \(c_x=(k+1)\sum_{i=0}^{\frac {kn(n+1)}{2}} f_{x-1,i}f_{n-x,i}-1\)。
标签:背包,20240913,ARC104,独立,区间,dp From: https://www.cnblogs.com/luyuyang/p/18535159