P5424 [USACO19OPEN] Snakes G

Legend says that thousands of years ago, Saint Patrick got rid of all the snakes in MooLand. However, the snakes have now returned! Saint Patrick’s Day is on March 17 every year, so Bessie wants to celebrate it by completely clearing MooLand of all snakes. Bessie is equipped with a net to catch $N$ groups of snakes lined up in a row ($1 \leq N \leq 400$). Bessie must catch all the snakes in each group in the order the groups appear in the line. Each time Bessie finishes catching one group of snakes, she puts them into cages, and then starts catching the next group with an empty net. A net of size $s$ means that Bessie can catch any group containing $g$ snakes, where $g \leq s$. However, whenever Bessie uses a net of size $s$ to catch a group of $g$ snakes, it wastes $s - g$ space. Bessie may choose the initial size of her net freely, and she may change the net size $K$ times ($1 \leq K < N$). Please tell Bessie the minimum possible total wasted space after she catches all groups of snakes.

The first line of input contains $N$ and $K$. The second line contains $N$ integers $a_1, \ldots, a_N$, where $a_i$ ($0 \leq a_i \leq 10^6$) is the number of snakes in the $i$-th group.

Output one integer: the minimum total wasted space for Bessie to catch all the snakes.

Bessie can set her net to have an initial size of $7$. After she catches the first group of snakes, she changes her net size to $9$, keeps this size until she catches the $3$-rd group, and then changes the net size to $3$. The total wasted space is $(7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2)=3$. Translated by ChatGPT 5