P2748 [USACO16OPEN] Landscaping P — 最小花费 / 不交叉匹配

题意

$N$ 个花坛，第 $i$ 个初始有 $A_i$ 单位泥土，希望变成 $B_i$ 单位。可以：

• 买 $1$ 单位放指定花坛，花费 $X$；
• 从任意花坛移走 $1$ 单位，花费 $Y$；
• 从花坛 $i$ 运 $1$ 单位到花坛 $j$，花费 $Z|i-j|$。

求最小总花费。$N\le {10}^5$，$0\le A_i,B_i\le 10$。

第一步：把每个花坛“拆成”点

对每个花坛 $i$，令 $d=A_i-B_i$：

• $d>0$：多出 $d$ 单位土 → 这是 $d$ 个源点，位置 $i$；
• $d<0$：缺少 $-d$ 单位土 → 这是 $-d$ 个目标点，位置 $i$；
• $d=0$：忽略。

于是问题变成：在一根数轴上有一串 $\pm$ 点，把一个源点 $s$ 和一个目标点 $t$ 配对（代价 $Z|s-t|$， 就是“移动”）；不配对的源点单独移走（代价 $Y$）；不配对的目标点单独购买（代价 $X$）。

我们可以把配对代价封顶：min(Z*|s-t|, X+Y)。因为若移动比“买 + 移走”还贵，那就等价于直接买再移走。 这样之后可以假设“数量较少的那一侧全部配对”（剩下的全是买/移走）。

第二步：不交叉性

最优匹配里可以假设边不交叉：若两条边交叉，把端点“交换”匹配后总代价不增（可用 $(i_1<i_2,j_1<j_2)$ 的交叉情况验证，长边、短边分情形讨论都成立）。

边不交叉意味着：每条边内部包含的源点数和目标点数必须相等（平衡），否则会有源点/目标点被迫跨界， 可以再优化。这给出一个分层结构。

第三步：按“层”分解（k = 每次 ±1）

把点按“高度层”摆放：从高到低，相邻两个符号相同的点往上/下爬一层。这样每一层内的点是严格交替 的（$+,-,+,-,\dots$）。每一层可以独立求解（因为不交叉保证了每层内部的匹配不会跨层交错）。

每层内：

• 若 $+$ 与 $-$ 数量相等 → 全部配对；
• 若多一个元素 → 它不参与配对（是“移走/购买”的那一个），其费用 ecost：
  • 多的是源点（+）：移走，$ecost=Y$；
  • 多的是目标点（−）：购买，$ecost=X$。

第四步：单层的 DP

层内点 $v[0..M-1]$ 交替，长度 $M$。我们做一次“不交叉全配对”的 DP：

results[j]（$j$ 为奇数）= 把 $v[0..j]$（一个平衡前缀）全部配对的最小代价。两种转移：

• 短边：$v[j]$ 与 $v[j-1]$ 直接配对（两者相邻），前面 $[0..j-2]$ 用 results[j-2]： Z*|v[j]-v[j-1]| + results[j-2]；
• 长边：$v[j]$ 与某个偶数下标 $i$ 配对，代价封顶为 $X+Y$；夹在 $(i,j)$ 内部的一串点按顺序两两配对， 前缀 $[0..i-1]$ 用 results[i-1]： X+Y + (前缀费用) + results[i-1]。

长边候选用双指针维护：i 从 $0$ 开始，只向前走，只要 X+Y <= Z*|v[j]-v[i+2]|（说明距离大得值得用长边）， 就更新最优长边值。短边/长边取 min。

层内可能奇数个元素，需要“留一个不配对”，所以再正向、反向各跑一遍 DP，枚举留点位置：

• 偶数个：results[M-1]；
• 奇数个：best = ecost + min(results[M-2], reverse_results[1])， 再对每个留点位置 i 取 min(best, results[i-1] + ecost + reverse_results[i+1])。

复杂度

每层 $O(\mathrm{层}\mathrm{长})$，所有层加起来 $O(N\cdot K)$，$K\le 10$，即 $\le {10}^6$。 空间 $O(N\cdot K)$，实测峰值约 $60\text{MB}$。

这题教会什么

1. 转化：把“搬土”的带宽问题，展开成数轴上一堆 $+/-$ 点的不交叉匹配；
2. 不交叉 + 分层：证明不交叉后，按“高度层”把问题分解成若干独立的小问题；
3. 带封顶的匹配 DP：配对代价 min(Z*dist, X+Y)，长边/短边分类讨论，双指针优化长边候选；
4. 正反双双跑 + 枚举留点：处理奇数个元素（有一个不被配对）的情形。