/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 575 点
問題文
文字列 S が与えられます。文字列 S に対して以下の操作を 0 回以上繰り返し行うことで得られる文字列の長さの最小値を求めてください。
- 文字列の中で
ofが連続する箇所および 0 以上 K 以下の整数 i を 1 つ選ぶ。その後、ofおよびその後ろに連続する i 文字を文字列から取り除く。
制約
- 0 \leq K < |S| \leq 300
- K は整数
- S は英小文字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S K
出力
答えを出力せよ。
入力例 1
keyofscience 3
出力例 1
7
4, 5 文字目に連続する of を選び、i = 3 とすることで keyofscience から ofsci を取り除き、 keyence を得ます。
操作の繰り返しにより文字列の長さを 6 以下にすることはできないため、7 が答えとなります。
入力例 2
oofsifffence 3
出力例 2
2
入力例 3
ooofff 5
出力例 3
0
入力例 4
okeyencef 4
出力例 4
9
Score : 575 points
Problem Statement
You are given a string S. Find the minimum length of a string that can be obtained by performing the following operation on the string S zero or more times.
- Choose a contiguous occurrence of
ofin the string and an integer i between 0 and K, inclusive. Then, remove theofand the following i characters from the string.
Constraints
- 0 \leq K < |S| \leq 300
- K is an integer.
- S is a string consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S K
Output
Print the answer.
Sample Input 1
keyofscience 3
Sample Output 1
7
By choosing the of formed by the fourth and fifth characters and setting i = 3, you can remove ofsci from keyofscience and get keyence.
It is impossible to reduce the length of the string to 6 or less by repeating the operation, so the answer is 7.
Sample Input 2
oofsifffence 3
Sample Output 2
2
Sample Input 3
ooofff 5
Sample Output 3
0
Sample Input 4
okeyencef 4
Sample Output 4
9