USACO 2019 US Open Contest, Gold Problem 1. Snakes

According to legend, St. Patrick banished all of the snakes in Mooland over a thousand years ago. However, snakes have since made their way back to Mooland! St. Patrick’s day was on March 17, so Bessie is going to commemorate St. Patrick by banishing all of the snakes from Mooland once and for all.

Bessie is equipped with a net to capture snakes distributed in NN groups on a line (1≤N≤400)(1≤N≤400). Bessie must capture every snake in every group in the order that the groups appear on the line. Each time Bessie captures a group, she can put the snakes in a cage and start with an empty net for the next group.

A net with size ss means that Bessie can capture any group that contains gg snakes, where g≤sg≤s. However, every time Bessie captures a group of snakes of size gg with a net of size ss, she wastes s−gs−g space. Bessie’s net can start at any size and she can change the size of her net KK times (1≤K<N)(1≤K<N).

Please tell Bessie the minimum amount of total wasted space she can accumulate after capturing all the groups.

INPUT FORMAT (file snakes.in):

The first line contains NN and KK. The second line contains NN integers, a1,…,aNa1,…,aN, where aiai (0≤ai≤1060≤ai≤106) is the number of snakes in the iith group.

OUTPUT FORMAT (file snakes.out):

Output one integer giving the minimum amount of wasted space after Bessie captures all the snakes.

SAMPLE INPUT:
6 2
7 9 8 2 3 2

SAMPLE OUTPUT:
3

Bessie’s net starts at a size of 7. After she captures the first group of snakes, she changes her net to a size of 9 and keeps that size until the 4th group of snakes, when she changes her net to size 3. The total wasted space is (7−7)+(9−9)+(9−8)+(3−2)+(3−3)+(3−2)=3.(7−7)+(9−9)+(9−8)+(3−2)+(3−3)+(3−2)=3.

Problem credits: Patrick Zhang

中文版

传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。

Bessie装备了一个捕网，用来捕捉NN组排成一行的蛇（1≤N≤4001≤N≤400）。Bessie必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当Bessie抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。

一个大小为ss的捕网意味着Bessie可以抓住任意包含gg条的一组蛇，其中g≤sg≤s。然而，每当Bessie用大小为ss的捕网抓住了一组gg条蛇，就意味着浪费了s−gs−g的空间。Bessie可以任意设定捕网的初始大小，并且她可以改变KK次捕网大小（1≤K<N1≤K<N）。

请告诉Bessie她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。

输入格式（文件名：snakes.in）：

输入的第一行包含NN和KK。第二行包含NN个整数a1,…,aNa1,…,aN，其中aiai（0≤ai≤1060≤ai≤106）为第ii组蛇的数量。

输出格式（文件名：snakes.out）：

输出一个整数，为Bessie抓住所有蛇的总浪费空间的最小值。

输入样例：
6 2
7 9 8 2 3 2

输出样例：
3

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

供题：Patrick Zhang