切换到宽版
  • 5270阅读
  • 0回复

求助! [复制链接]

上一主题 下一主题
 
只看楼主 倒序阅读 0 发表于: 2010-03-06
拴马

齐弗森有N匹马,其中有一些是黑色的而另一部分是白色的。每天他都要牵着他的N匹马出去玩耍,然后带着他们排成一条长队回到马圈。今天他想重新安排他的马,把这些马合理地放入M个马圈。使得没有马圈是空的,也没有马留在外面。

为了不弄混,他的马编号为1。。N,而马圈同样编号为1.M。他决定让马按照顺序依次送入马圈中,既对于马IJI<J),马J只能和马I住,同一个马圈或者住编号更大的马圈。

马儿不太喜欢和太多的马住在同一个马圈,所以每一个马圈都有一个马儿们不喜欢的值。假设该马圈有A只白马和B只黑马,则不满意值为A×B。总的不满意值是所有马圈的不满意值之和。

齐弗森要怎样安排他的马才能让其总不满意值最小呢?

输入格式

第一行为NM(n<=1000,m<=n).接下来有N行,每行一个数字0或多或1,I1行为0,则表示马I是白马,为1则表示马I为黑马。

输出格式

仅一行,最小不满意值之和。

样例输入:

6 3

1

1

0

1

0

1

样例输出:

2

快速回复
限100 字节
 
上一个 下一个