| 比赛场次 | 162 |
|---|---|
| 比赛名称 | 20120807 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2012-08-07 08:20:00 |
| 结束时间 | 2012-08-07 12:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 |
| 题目名称 | 宁采臣的书架 |
|---|---|
| 输入输出 | arrangement.in/out |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 33 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 王者自由 |
MMMMMMMMMM | 0.000 s | 0.00 MiB | 0 |
 Makazeu |
WWWWWWWWWW | 0.004 s | 0.29 MiB | 0 |
 Truth.Cirno |
WTTTTTTTTT | 28.562 s | 0.29 MiB | 0 |
【题目描述】
宁采臣终于带着宝贝回到了家，发现家里的书架乱成一团了！这让这个书生实在是无法忍受。他要整理一下了。他的书架上一共有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