一些 dp 题

CYEZ 弹珠

key：问题转换，完全背包

先每个组分一个小球。等价于 $n-k$ 拆分为任意个 $[1,k]$ 的数的方案数。

本质是根据面积的转换，直观解释：

完全背包即可。代码。

No Bug No Game

key：exchange argument，背包

子序列

SOL1：

key：LIS，动态开点，线段树

记 $f_i$ 为以 $a$ 中第 $i$ 个数结尾的最长的好的子序列。

$$f_i=\underset{j<i,a_j\cdot b_{f_j}\le a_i}{\max }{f}_j+1$$

可以用动态开点权值线段树优化。代码。

CYEZ 01 矩阵

key：问题转换

两张 $n$ 个点的二分图 A B，$(x,y)=1$ 视为 A 中点 $x$ 向 B 中点 $y$ 连边，这样二分图中显然会形成若干个环，环为偶环且大小 $>2$。题目中交换行列后不同相当于在二分图中交换点的编号，转换为无标号环凑成 $2n$ 个点的方案数。等价于 $>1$ 的数无序组成 $n$ 个点的方案数。

代码

Bribing Friends G

key：贪心 + dp

确定选择奶牛方案时，甜筒一定优先作用于 $x$ 较小的奶牛。那么按 $x$ 排序后，最终的答案一定形如：用甜筒处理前几个，用甜筒和钱混合处理某一个，用钱处理后几个。

分别 01 背包处理，枚举断点即可。

代码

特殊的区间 dp 类问题——折线类问题

轨迹类似折线的一类问题，这类问题通常在区间 dp 的基础上记录左 / 右端点。

The Cow Run G/S

模板。

根据 $f(l,r,0/1)$ 总是同时出现的性质可以少讨论一种情况。

代码

更简单的一种实现，记 $f(l,r,0/1)$ 表示为当前点左端剩 $l$ 个，右端剩 $r$ 个点，位于左 / 右端点的最小代价。每次决策向左或向右即可。代码。

关路灯

模板基础上套个前缀和。

代码

Turning in Homework G

折线类 dp 基础上有一个等待机制。

key：贪心 + dp，区间 dp

贪心：一定先处理外端的点。证明：先处理外端点可以使处理内端点等待的时间变短。相反，先处理内端点后还要出去处理外端点导致重复移动。

故设计 $f(l,r,0/1)$ 表示刚刚处理完 $l/r$，$[l,r]$ 未处理（不包括 $l/r$）的最小代价。

考虑转移，以 $f(l,r,0)$ 为例：
如图，1 优于 2 的原因：$f(l-1,r,0)\le f(l-1,r,1)+dis(l-1,r)$。3 优于 4 同理。

故转移只考虑 $f(l-1,r,0)$ 以及 $f(l,r+1,1)$ 即可。

代码

JOI2020 Collecting Stamps

key：破环为链，区间 dp

先看链的情况。采用一般折线类方式设计 $f(l,r,0/1)$ 会发现这样无法推得最优解，因为转移时不一定是最短 / 最多。考虑升维。记 $f(l,r,i,0/1)$ 表示获得了 $i$ 个的最短时间。转移类似前两题，答案取一个最大的可能 $i$ 即可。

然后做一个等价转换——破环为链。将序列扩展为长 $2n$ 的序列，对长度不超过 $n$ 的区间做转移 / 求答案。对于 $l=r$ 边界情况，距离为到 $L$ 或到 $0$ 的距离。

代码