双色马

成绩 100 开启时间 2016年05月30日 星期一 15:10
折扣 0.8 折扣时间 2016年05月30日 星期一 15:10
允许迟交 是 关闭时间 2016年05月30日 星期一 15:10
输入文件 Binhorse.in 输出文件 Binhorse.out

【题目描述】双色马（Binhorse.cpp/c/pas）URAL 1167  

       邪狼负责管理所有的战马，每天，他放出所有战马，任它们奔跑嬉戏。到了晚上，邪狼把所有马带回马厩，邪狼把它们排在一条直线上然后跟着他回厩。由于马儿们很累，邪狼尽量不让它们移动。所以他发明了一个算法：他把前P1匹马放在第一个马厩，下面P2只马放在第二个马厩，等等，而且，他不想K个马厩任何一个是空的，并且没有马被留在外边。邪狼有黑白两种颜色的马，两种颜色的马相处不好。如果有i匹黑马和j匹白马同在一个马厩中，那么这个马厩的忧愁系数为i×j。总忧愁系数是所有马厩忧愁系数的和。恢愁系数过大会表现在马儿互相打架或者马儿彻夜长嘶，这会引起修罗王的不满，邪狼可能要被惩罚，后果您也可以想象出来，很严重的！故请决定一种方法把N匹马放进K个马厩使得总忧愁系数最小。

 　【输入格式】

第一行是N（1≤N≤500）和K（1≤K≤N），下面N行有N个数第i行是第i只马的颜色，1代表黑色，0代表白色。

【输出格式】

最小的总忧愁系数。

【输入样例】

 6 3

1

1

0

1

0

1

 【输出样例】

2

  【样例说明】

将前2匹马放在第一个马厩，下面3匹马放在第二个马厩，最后一匹马放在第三个马厩。

【时间限制】

10秒

【内存限制】

16MB