马棚问题【动态规划 DP专题训练】 1262

每天，小明和他的马外出，一边跑一边玩。当结束的时候，小明必须带所有的马返回马棚，他有k个马棚。小明把他的马排成一排，然后跟随它们走向马棚。因为它们非常疲劳，小明不想让他的马做过多移动。因此他想了一个方法；将马按照顺序放在马棚中，后面的马放的马棚序号不会大于前面的马放的马棚序号。而且，他不想他的k个马棚中任何一个空置，也不想任何一匹马在外面。已知共有黑、白两种马，而且它们相处得并不十分融洽。如果有i匹白马和j匹黑马在一个马棚中，那么这个马棚的不愉快系数将是i*j。确定一种方法把n匹马放入k个马棚中，使得所有k个马棚的不愉快系数系数总和最小。

输入有二行： 第一行有二个整数n和k，互相之间以一个空格分隔。（1≤n≤500，1≤k≤n）。 第二行有n个数，分别表示每匹马的颜色，以1代表黑色，0代表白色。

输出只有一行，该行只有一个整数，表示最小的不愉快系数总和。