题解

问题分析

这是一个动态规划 + 双端队列优化的问题。我们需要对每个前缀 $i$ 计算灌溉前 $i$ 株植物的最小费用。

关键观察

1. 水渠特性：水渠 $i$ 同时灌溉植物 $i$ 和 $i+1$，费用为 $c_i \times k$
2. 水量约束：每个植物 $i$ 需要至少 $w_i$ 单位水
3. 费用函数：费用是关于水量的分段线性凸函数

算法思路

维护凸包 + 双端队列优化：

数据结构设计

• I 结构：维护凸包的双端队列，支持反转和线性变换
• x：存储水量转折点
• k：存储斜率变化量
• f0, fv：函数在 0 和 V 处的值
• d0, dv：函数在 0 和 V 处的斜率

核心操作

1. 斜率调整：当 $d_0 < 0$ 时，从左侧移除负斜率段
2. 水量约束：当 $x.Back() \geq w[i]$ 时，从右侧调整以满足新植物的水量需求
3. 状态转移：添加新水渠时更新费用函数

算法步骤

1. 初始化：处理第一株植物
2. 循环处理：对于每个新植物 $i = 2$ 到 $n$：
   • 调整左侧负斜率
   • 调整右侧满足水量约束
   • 输出当前前缀的最小费用
   • 添加新水渠，更新状态

复杂度分析

• 每个植物：均摊 $O(1)$ 次队列操作
• 总复杂度：$O(N)$

关键函数说明

I 结构操作

• Rev()：反转队列顺序
• Apply(x)：应用线性变换 $f(x) \to -f(x) + C$
• F(x), If(x)：正向/反向坐标变换

水量约束处理

while (!x.Empty() && x.Back() >= w[i]) {
    fv -= dv * (lst - x.Back());
    lst = x.Back();
    dv -= k.Back();
    x.PopBack();
    k.PopBack();
}

负斜率修正

while (d0 < 0) {
    f0 += d0 * (x.Front() - lst);
    lst = x.Front();
    d0 += k.Front();
    x.PopFront();
    k.PopFront();
}

样例验证

样例1：$w = [39,69,33], c = [30,29]$

• 前2株：使用水渠1 69次，费用 $30 \times 69 = 2070$
• 前3株：水渠1 39次 + 水渠2 33次，费用 $39 \times 30 + 29 \times 33 = 2127$
• 输出正确

样例2：$w = [33,82,36], c = [19,1]$

• 前2株：水渠1 82次，费用 $19 \times 82 = 1558$
• 前3株：优化后费用 676
• 输出正确

算法标签

• 动态规划
• 凸包维护
• 双端队列优化
• 分段线性函数
• 斜率优化