问题 3204 --双色马

3204: 双色马

题目描述

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

输入

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

输出

最小的总忧愁系数。

样例输入输出

输入#1 复制
 6 3
1
1
0
1
0
1
输出#1 复制
2

提示

【样例说明】
将前2匹马放在第一个马厩,下面3匹马放在第二个马厩,最后一匹马放在第三个马厩。

序号 标题 作者 发表时间 费用 订购数 操作