题目 2253:
蓝桥杯算法提高-和谐宿舍2
时间限制: 2s
内存限制: 192MB 提交: 172 解决: 86
题目描述
我的某室友学过素描，墙上有n张他的作品。这些作品都是宽度为1，高度不定的矩形，从左到右排成一排，且底边在同一水平线上。
宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。
宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。
在能够把所有作品和谐掉的前提下，我们希望这些木板的面积和最小，问最小面积和。
输入格式
第一行两个数n和m，表示作品数和木板数；
第二行n个数Hi，表示从左到右第i个作品的高度。
对于30%的数据：1<=n，m<=10；
对于100%的数据：1<=n，m<=100，1<=Hi<=10000。
输出格式
一行一个数ans，表示答案。
样例输入
5 2 4 2 3 5 4
样例输出
22