Problem : 62 - Words

Problem Statistics

Solved Member: 20　　Submission: 96　　User Tried: 25

Statement:

你看過龍使嗎？那是一部愛與熱血的kuso奇幻童話故事。

傳聞中，卡恩國國王在臨死前，將他的龍封印在他的陵墓前，而想成為龍使的你，一聽到這個消息，就迫不及待的衝向了他的陵墓，經過重重的障礙，你終於到達了封印龍的地方，當你迫不及待的想解開封印時，你突然被封在一個魔法陣裡，而解開的方法就是喊出卡恩國國王萬歲。

要喊幾次代表你的誠意真是一個問題，聰明的你發現了地上有一段文字：

我們定義一個字串的簡單度為該字串連續區段數，

例：ABAACBBBA 的簡單度為6 ( A|B|AA|C|BBB|A )

給一個長 N 的字串 S，和數字 K，假設從 S 至多改 K 個字母，可以使你的簡單度為最低 C ，你只要大喊卡恩國國王萬歲 C 次，眼前那隻龍就是你的了。

聰明的你已經拿出了隨身攜帶的電腦，準備算出 C 是多少了，進而得到卡恩國國王的龍。

Input:Output:

第一行有兩個數字，分別為 N 與 K (1 <= N <= 1000, 0 <= K <= N)。
第二行有一個長度為 N 的字串。

請輸出最簡單度 C 。

Sample Input:Sample Output:

9 3
ABAACBBBA

HINT:

解開封印後你赫然發現，這個卡恩國國王並不是弗利茲。

Source:

PA 2006 Round 4

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	32768kb
1-1	1000ms	32768kb	10
1-2	1000ms	32768kb
2-1	1000ms	32768kb	10
2-2	1000ms	32768kb
3-1	1000ms	32768kb	10
3-2	1000ms	32768kb
4-1	1000ms	32768kb	10
4-2	1000ms	32768kb
5-1	1000ms	32768kb	10
5-2	1000ms	32768kb
6-1	1000ms	32768kb	10
6-2	1000ms	32768kb
7-1	1000ms	32768kb	10
7-2	1000ms	32768kb
8-1	1000ms	32768kb	10
8-2	1000ms	32768kb
9-1	1000ms	32768kb	10
9-2	1000ms	32768kb
10-1	1000ms	32768kb	10
10-2	1000ms	32768kb