Problem D
Squash
Göran har börjat spela squash med sina vänner. Under en dag hinner han spela $N$ matcher. Görans mål är naturligtvis att vinna så många matcher och förlora så få matcher som möjligt. Hans nöjdhet efter en dag av squashspelande är lika med antalet matcher han vunnit minus antalet matcher han förlorat.
Förutom att bli bättre på squash och vinna fler matcher har Göran ett extra knep för att öka sin nöjdhet: han hävdar att det bara är under $K$ olika serier av sammanhängande matcher som han spelade seriöst. Endast dessa matcher räknas in i uträkningen av hans nöjdhet. Göran väljer alltid dessa $K$ matchserier för att maximera sin nöjdhet.
En matchserie består alltid av samtliga matcher mellan den $i$:te och den $j$:te matchen för något valt $i$ och $j$, men Göran får låta en (eller alla!) matchserier vara tomma (t.ex. kanske han tog en väldigt seriös vattenpaus istället). De sammanhängande matchserierna han väljer får inte överlappa, d.v.s. varje spelad match får vara del av högst en vald matchserie.
Givet matchhistoriken för en dag, vad blir Görans nöjdhet om han väljer matchserierna optimalt?
Indata
Den första raden innehåller de två heltalen $N$ och $K$ ($1 \le K \le N \le 1\, 000$), antalet matcher och antalet seriösa matchserier.
Nästa rad innehåller en sträng med $N$ tecken, resultaten av de matcher Göran spelade. Det $i$:te av dessa tecken är V om Göran vann den $i$:te matchen, och F om han förlorade den.
Utdata
Skriv ut ett enda heltal: den maximala nöjdheten Göran kan uppnå.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$10$ |
$K = 1$ |
|
$2$ |
$20$ |
$K = 2$ |
|
$3$ |
$30$ |
$K = 3$ |
|
$4$ |
$40$ |
Inga ytterligare begräsningar. |
Förklaring av exempelfall
I det första exempelfallet är det optimalt att välja den enda sammanhängande serien till att bestå av samtliga matcher. Bland dessa vanns $4$ och $1$ förlorades, vilket ger nöjdheten $3$.
I det andra exempelfallet spelade Göran seriöst under två matchserier. Han kan då välja de två första samt de två sista matcherna som sina serier, varav samtliga är vinster. Detta ger nöjdheten $4$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 VVFVV |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 2 VVFVV |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
19 3 VVFFVFVVVFVVVFFFFVV |
9 |
| Sample Input 4 | Sample Output 4 |
|---|---|
1 1 F |
0 |
