| 题目名称 | 993. [NOIP 2010冲刺三]宁采臣的书架 |
|---|---|
| 输入输出 | arrangement.in/out |
| 难度等级 | ★ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 33 MiB |
| 测试数据 | 10 |
| 题目来源 |
 sywgz
于2012-08-06加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：10， 通过率：20% | ||||
 KZNS |
100 | 1.525 s | 2.68 MiB | C++ |
 Ezio |
100 | 3.482 s | 2.70 MiB | C++ |
|
KZNS |
10 | 1.251 s | 1.88 MiB | C++ |
|
KZNS |
10 | 1.265 s | 2.08 MiB | C++ |
|
Ezio |
10 | 1.606 s | 2.70 MiB | C++ |
|
Ezio |
10 | 1.609 s | 2.70 MiB | C++ |
|
Ezio |
0 | 0.001 s | 2.70 MiB | C++ |
|
Ezio |
0 | 0.002 s | 2.70 MiB | C++ |
|
KZNS |
0 | 1.529 s | 2.08 MiB | C++ |
|
Ezio |
0 | 1.586 s | 2.70 MiB | C++ |
| 本题关联比赛 | |||
| 20120807 | |||
| 关于 宁采臣的书架 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
喵喵喵~
| ||||
|
跪求大神代码@Ezio
 woca
2014-10-14 22:49
2楼
| ||||
|
沙发
 GeekTao
2014-10-13 20:42
1楼
| ||||
【题目描述】
宁采臣终于带着宝贝回到了家，发现家里的书架乱成一团了！这让这个书生实在是无法忍受。他要整理一下了。他的书架上一共有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