AtCoder Beginner Contest 217

Posted on Edited on In

AtCoder Beginner Contest 217

Easiest ABC ever!

H - Snuketoon

考虑维护最小伤害的函数\(f_n(x)\)

\[ f_i(x) = \underset{x-\Delta t \leq x_0 \leq x + \Delta t} {\min} f_{i-1}(x_0) + g_i(x) \]

该函数为分段一次函数，且满足凸性，用multiset或者堆维护分段斜率即可。