和 Aug 9th 的杂题不太能合并，所以分开了

C. 扫地机器人

http://222.180.160.110:61235/contest/6502/problem/3

题意：给定 \(n\) 堆货物，每堆货物有重量 \(v_i\) 和一个参数 \(a_i\)。有一个初始负载为 \(0\)、负载上限为 \(c\) 的机器人，从 \(1\) 到 \(n\) 遍历这些货物，对每一处货物执行以下操作，直到清空这堆货物：

• 当前负载未满：可以选择进行装载直到达到负载上限，或货物清空。花费 \(a_i\) 的代价。
• 不管当前负载满没满：可以选择清空当前负载，花费 \(b\) 的代价。

每一处可以任意操作，要求遍历完之后机器人负载为 \(0\)，问最小代价。\(n\le 2\times 10^5,c\le 10^9\)。

题面是我重构过的，原来的题面太有歧义了。

考虑暴力，可以想到令 \(f_{i,j}\) 表示处理完 \(i\) 过后负载为 \(j\) 的最小代价（显然 \(f_{i,c}\) 和 \(f_{i,0}\) 是等效的，故舍弃前者）。记 \(k=\left\lceil\dfrac {v_i}c\right\rceil\)，那么有：

\[ f_{i,(j+v_i)\bmod c}\gets f_{i-1,j}+k\cdot a_i+(k-1)\cdot b + (a_i+b)\cdot [j + a_i\bmod c \ge c]\\ f_{i,0}\gets f_{i,j}+b \]

发现 \(f_{i-1}\) 和 \(f_i\) 之间是存在对应关系的，所以考虑直接继承（真实的 \(0\) 应该位于 \(-s_i\) 的位置），再做全局加、区间加，\(f_{i,0}\) 的转移是区间 min，线段树维护即可；每次只会新增一个状态，动态开点即可。