#2966. 「COCI 2010.03.06」ZUMA

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 COCI 2010.03.06 T4「ZUMA

Mirko 将 N 颗弹子排成一排,依次编号为 1\ldots N i 号弹子的颜色为 c_i 。他发现,如果他触摸 \ge K 颗连续的弹子,且这些弹子的颜色相同,魔法会使这些弹子消失;此后,这 K 颗弹子前面的弹子便与这 K 颗弹子后面的弹子相邻。

Mirko 家里有很多弹子,他想在这 N 颗弹子之间(也可以在开头的弹子前面或末尾的弹子后面)插入尽可能少的弹子,使得这 N 颗弹子+插入的所有弹子消失。

输入格式

第一行: N,K
第二行: c_1\ldots c_N

输出格式

一行,一个整数,表示他至少要插入几颗弹子。

样例

样例输入 1

2 5
1 1

样例输出 1

3

样例输入 2

5 3
2 2 3 2 2

样例输出 2

2

样例输入 3

10 4
3 3 3 3 2 3 1 1 1 3

样例输出 3

4

数据范围与提示

1\le N\le 100, 2\le K\le 5, 1\le c_i\le 100 .