UOJ Logo Sharp Sword 剑锋 OI

SSOI

#1123. 帮助Bsny(help)

统计

时间限制:1S / 空间限制:256MB

【问题描述】

  Bsny的书架乱成一团了,帮他一下吧! 
  他的书架上一共有n本书,我们定义混乱值是连续相同高度书本的段数。例如,如果书的高度是30,30,31,31,32,那么混乱值为3;30,32,32,31的混乱值也为3。但是31,32,31,32,31的混乱值为5,这实在是太乱了。 
  Bsny想尽可能减少混乱值,但他有点累了,所以他决定最多取出k本书,再随意将它们放回到书架上。你能帮助他吗?

【输入格式】

第一行两个整数n,k,分别表示书的数目和可以取出的书本数目。 
接下来一行n个整数表示每本书的高度

【输出格式】

仅一行一个整数,表示能够得到的最小混乱值。

【输入样例1】

5 1 
25 26 25 26 25

【输出样例1】

3

【数据范围】

20%的数据:1≤n≤20,k=1。 
40%的数据:书的高度不是25就是32,高度种类最多2种。 
100%的数据:1≤k≤n≤100,注意所有书本高度在 [25,32]。

【题目来源】

JZOJ3853