251218 贪心构造选讲 && 251220 动态规划选讲

AT_agc054_d [AGC054D] (ox)

发现 o 没有任何限制，x 要求其必须被包含在一个括号中，其余括号必须匹配成合法括号序列。将所有 ( 和 ) 拿出来，先把他们移动成合法括号序列，然后放回原序列中；通过手模可以证明如果继续交换两个 )(，显然是不优的，因为不会改变 x 被包含的状态。并且通过手摸发现交换 ox 也是不优的。

由于交换的次数等于逆序对数，而逆序对数等于左右括号子序列内部形成的逆序对，加上 ox 和左右括号形成的逆序对。对两个子序列进行归并，容易在 \(O(n^2)\) 的状态里计数逆序对数。

CF1408F Two Different

发现 \(2^k\) 是好做的，其余情况顶着左端点和右端点各做一遍 \(2^k\) 即可。

P13552 鱼类考古学

显然先进行按位与再进行加法（可以使用调整法证明），问题转化为将序列分为 \(k\) 组，最大化每组按位与的和。考虑按位贪心，如果可以不删去任何 \(1\)，那么就把每个 \(1\) 都分一组，剩下的转化为子问题；否则把所有 \(0\) 先合并成一组，然后转化成子问题。这样总是可以卡到 \(1\) 数量的上界。

CF1175G Yet Another Partiton Problem

可以单调栈套李超线段树。但是我看的题解写的 cdq。考虑分治，可以把区间 \(\max\) 拆成左侧区间的后缀 \(\max\) 和右侧区间的前缀 \(\max\)。分讨二者，搞一个合适的转移顺序，可以用斜率优化。时间复杂度 \(O(n\log n)\)。

P9338 [JOIST 2023] 合唱 / Chorus

给定一个 01 序列，称一个子序列是合法的，当且仅当其由 \(\frac{len}{2}\) 个 0 和 \(\frac{len}{2}\) 个 1 拼接而成（0 在前 1 在后）。称一次操作为交换两个相邻元素，你需要用最少的操作，使得原序列可以被划分为 \(k\) 段合法子序列。

考虑如何求出一个序列的最小划分段数。发现有贪心策略：把前缀极长 0 连续段都匹配后面的 1，肯定最优。考虑继续刻画这个贪心：对每个 1 维护出其前面的 0 的数量 \(b_i\)，然后有一个变量 \(x=1\)，每次划分形如 \(x\gets b_x+1\)。

然后一次操作形如将一个 \(b_i\)++，并且需要保持单调不降。发现可以设计出一个二维 dp，每次枚举下一个位置往哪跳，然后把中间不达标的 \(b_i\) 全都拔高：

\[ f_{i,j}+\sum_{x=i}^{t-1}\max(0,t-b_x)\to f_{t,j+1} \]

考虑优化，把 \(\sum\) 拆开：

\[ \sum_{x=i}^{t-1}\max(0,t-b_x)=\sum_{x=1}^{t-1}\max(0,t-b_x)-\sum_{x=1}^{i-1}\max(0,t-b_x) \]

为了更加好做我们可以钦定 \(t\ge b_i\)，这样后一项就变成了 \(\sum_{x=1}^{i-1}t-b_x=(i-1)t-s_{i-1}\)。记 \(p_t=\sum_{x=1}^{t-1}\max(0,t-b_x)\)，那么最终转移式就变成了：

\[ f_{i,j}-s_{i-1}+(i-1)t+p_t\to f_{t,j+1} \]

可以斜率优化做到 \(O(n^2)\)，但这还不够。发现满足四边形不等式的区间代价，答案关于段数具有凸性，因此可以 wqs 二分。时间复杂度 \(O(n\log n)\)。

P9339 [JOIST 2023] 曲奇 / Cookies

考虑给定盒子大小序列 \(x_{1\sim k}\)（降序排列），如何判定合法。有显然的贪心策略：每次取剩余容量前 \(a_i\) 大的盒子放。那么注意到一个必要条件如下：

\[ \forall t,~\sum_{i=1}^{n}\min(a_i,t)\le\sum_{i=1}^{t}x_i\\ \sum_{i=1}^{k}x_i=\sum_{i=1}^{n}a_i \]

然而它也是充要的，因为根据上面的贪心策略将 \(x_1\) 匹配后，仍然满足上面的条件。

于是设 \(f_{i,j,k}=0/1\) 表示考虑了前 \(i\) 种 \(size\)，一共装了 \(j\) 个盒子，总和为 \(k\) 是否可行（因为没有单调性）。可以 bitset 优化到 \(O(\frac{n^2}{w})\)。如果我们将 \(b_i\) 从大到小排序，那么 \(j\le\frac{n}{b_i}\)，形如一个调和级数，因此时间复杂度为 \(O(\frac{n\log n}{w})\)。

AT_abc290_h [ABC290Ex] Bow Meow Optimization

考虑观察性质。注意到一定存在一个划分点，使得左右两侧猫的数量相差不超过 \(1\)，狗的数量也相差不超过 \(1\)。又注意到划分点两侧的 \(a_i\) 也一定是单调的。以上两个性质都可以使用调整法证明。现在就可以直接 \(O(n^3)\) dp 了。

设 \(d_i\) 表示第 \(i\) 个位置对应的 \(|x-y|\)。又注意到 \(\sum d\) 是常数，因此优先给 \(a_i\) 大的动物分配较小的 \(d_i\)。具体的，对于猫直接放到划分点左侧，对于狗直接放到划分点右侧，如果某一侧满了就把多余的放到还没满的那一侧进行归并排序即可，时间复杂度 \(O(n\log n)\)。

P9132 [USACO23FEB] Watching Cowflix P

不知道 \(O(n\log n)\) 的做法怎么实现。

考虑根号分治，由于 \(k\) 时连通块数量不超过 \(\frac{n}{k}\)，设置阈值 \(B\)，对于 \(k\ge B\)，提前 dp 出每个连通块数量的最小代价；对于 \(k<B\) 直接暴力即可。需要卡常。