[NOIP2010冲刺三]宁采臣的书架

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 arrangement.in 输出文件 arrangement.out

【题目描述】

宁采臣终于带着宝贝回到了家,发现家里的书架乱成一团了!这让这个书生实在是无法忍受。他要整理一下了。
他的书架上一共有n本书。我们定义混乱值是连续相同高度书本的段数。例如,如果书的高度是30,30,31,32,那么混乱值为3;30,32,32,31的混乱度也是3;但31,32,31,32,31的混乱度是5,这实在是太乱了。
宁采臣想尽可能地减少混乱度,但他有点累了,所以他决定最多取出K本书,再随意将他们放到书架上。你能帮助他想想办法吗?


【输入格式】

最多会有20组测试数据。每组测试数据开头为两个整数n, k(1≤k≤n≤100),表示总共有n本书,最多可以进行k次搬书操作。接下来一行有n个整数,表示每本书的高度,从左到右。每本书的高度是25到32之间的整数。最后一组数据后有一行n=k=0。


【输出格式】

对于每一组数据,输出case标号和最终最小的混乱度。在每组数据后打印一个空行。


【输入样例】

5 2

25 25 32 32 25

5 1

25 26 25 26 25

0 0


【输出样例】

Case 1: 2


Case 2: 3


【数据范圈】

注意:时限3s 空间为32768k