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

中文版

傳說，數(shù)千年前圣帕特里克消滅了哞爾蘭所有的蛇。然而，蛇們現(xiàn)在卷土重來了！圣帕特里克節(jié)是在每年的3月17日，所以Bessie要用徹底清除哞爾蘭所有的蛇來紀(jì)念圣帕特里克。

Bessie裝備了一個捕網(wǎng)，用來捕捉NN組排成一行的蛇（1≤N≤4001≤N≤400）。Bessie必須按照這些組在這一行中出現(xiàn)的順序捕捉每一組的所有蛇。每當(dāng)Bessie抓完一組蛇之后，她就會將蛇放在籠子里，然后帶著空的捕網(wǎng)開始捕捉下一組。

一個大小為ss的捕網(wǎng)意味著Bessie可以抓住任意包含gg條的一組蛇，其中g(shù)≤sg≤s。然而，每當(dāng)Bessie用大小為ss的捕網(wǎng)抓住了一組gg條蛇，就意味著浪費(fèi)了s?gs?g的空間。Bessie可以任意設(shè)定捕網(wǎng)的初始大小，并且她可以改變KK次捕網(wǎng)大小（1≤K<N1≤K<N）。

請告訴Bessie她捕捉完所有組的蛇之后可以達(dá)到的總浪費(fèi)空間的最小值。

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

輸入的第一行包含NN和KK。第二行包含NN個整數(shù)a1,…,aNa1,…,aN，其中aiai（0≤ai≤1060≤ai≤106）為第ii組蛇的數(shù)量。

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

輸出一個整數(shù)，為Bessie抓住所有蛇的總浪費(fèi)空間的最小值。

輸入樣例：
6 2
7 9 8 2 3 2

輸出樣例：
3

Bessie可以設(shè)置她的捕網(wǎng)開始時大小為7。當(dāng)她抓完第一組蛇之后，她將她的捕網(wǎng)的大小調(diào)整為9，保持這個大小直到抓完第4組蛇，再將捕網(wǎng)大小調(diào)整為3。總浪費(fèi)空間為(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