CF1809F Traveling in Berland
Alex_Wei
·
·
题解
CF1809F Traveling in Berland
因为油价只有 1 或 2，所以遇到 1，我们一定能加满就加满，实在没油才会加 2。
不妨钦定到每个 1 时油箱恰好为空。如果不为空，则当前油箱里的油的单价不小于 1，替换为当前城市的油不劣。
考虑从城市 i 出发到另一个城市 j 的代价 f(i, j)，满足中途没有 1，且出发前和到达后油箱均为空。设距离为 d。当出发城市油价为 2 时，代价为 2d。当出发城市油价为 1 时，若 d\leq k，代价为 d，否则代价为 2d - k。
破环成链，考虑 i\to i + n 中途的所有油价为 1 的城市 p_1, p_2, \cdots, p_k，则 f(i, p_1) + f(p_k, i + n) + \sum_{j = 1} ^ {k - 1} f(p_j, p_{j + 1}) 即为所求。
倍增，设 f_{i, j} 表示从 j 出发跳 2 ^ i 步（每一步跳到下一个 1）到达的城市及对应代价。时间复杂度 \mathcal{O}(n\log n)。代码。
因为出发城市和到达城市单调增，所以双指针维护可做到 \mathcal{O}(n)。