马棚问题

Time Limit: 2 Sec  Memory Limit: 64 MB

Submit: 292  Solved: 74

Description

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

Input

多个测试组，每组测试第一行有2个数字：n( 1 <= n <= 500)和k( 1 <= k <= n). 接下来的n行是n个数，在这些行中的第i行代表队列中的第i匹马的颜色：1意味着马是黑色的，0则是白色的。处理到结束。

Output

对每组测试数据输出一行，只输出一个数字，代表系数总和可能达到的最小值

Sample Input

6 3110101 第一次独立完成的并AC了的dp,第一次没AC,就把no.1定义的全局变量放到main里，结果竟然通过了，这真心有点无语。no.2是AC版。no.1:

1 #include
       
         2 #include
        
          3 #include
         
           4 #define INF 1<<30 5 int horse,stable; 6 int color[600]; 7 int white[500],black[500]; 8 int dp[501][501]; 9 10 int min(int a,int b)11 {12     return a
         
        
       

no.2:(感觉就是"数字游戏"的简化版)

1 #include
       
         2 #include
        
          3 #include
         
           4 #define INF 1<<30 5  6 int min(int a,int b) 7 { 8     return a