P5424 [USACO19OPEN] Snakes G

传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的 3 月 17 日，所以 Bessie 要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。 Bessie装备了一个捕网，用来捕捉 $ N $ 组排成一行的蛇（ $ 1 \leq N \leq 400 $ ）。Bessie 必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当 Bessie 抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。 一个大小为 $ s $ 的捕网意味着 Bessie 可以抓住任意包含 $ g $ 条的一组蛇，其中 $ g \leq s $ 。然而，每当 Bessie 用大小为 $ s $ 的捕网抓住了一组 $ g $ 条蛇，就意味着浪费了 $ s-g $ 的空间。Bessie 可以任意设定捕网的初始大小，并且她可以改变 $ K $ 次捕网大小（ $ 1 \leq K

无

无

Bessie 可以设置她的捕网开始时大小为 $7$。当她抓完第一组蛇之后，她将她的捕网的大小调整为 $9$，保持这个大小直到抓完第 $3$ 组蛇，再将捕网大小调整为 $3$。总浪费空间为 $ (7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2)=3 $ 。