CCC2009 Dinner之Zuma2 - Problem

Description

类似于zuma游戏，给定一排N个珠子，已知每个珠子的颜色（原题中颜色只有2种），以及一个整数K。问你最少进行多少次操作，可以把这些珠子全部消去。每次操作是：选择连续的一段，它们必须是包含同一种颜色，并且长度不小于K，将它们消去，左右两边的合并。（不会自动消去，产生链式反应。）如果不能完成，输出-1即可。数据规模：N不超过100，K不超过6。

Input

Output

Sample Input

7 2
GHHGHHG

Sample Output

Hint

First send theﬁ rst pair of Hs to dinner,leaving GGHHG.Thens end the second pair of
Hs to dinner,leaving GGG;ﬁnally,send inthe group of Gs.It might be coincidental that
the two pairs of Helpﬁle programmers entered the cafeteria successively.

Source

2009 Canadian Computing Competition Stage2 Day1 Question

黑暗爆炸OJ

DARKBZOJ

#2220. CCC2009 Dinner之Zuma2