#PU900. USACO 2019 January Contest, Platinum — Problem 1. Redistricting

    ID: 1522 传统题 文件IO:redistricting 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan19来源:usaco.orgscoring:equal_test_cases枚举

USACO 2019 January Contest, Platinum — Problem 1. Redistricting

USACO 2019 January Contest, Platinum — Problem 1. Redistricting

题目描述

The cow mega-city Bovinopolis is redistricting! -- always a contentious political process between the two major cow breeds (Holsteins and Guernseys) living there, since both breeds want to make sure they retain sufficient influence in the Bovinopolis government. The greater metropolitan area of Bovinopolis consists of a line of NN pastures (1≤N≤3⋅1051 \leq N \leq 3 \cdot 10^5), each containing a single cow, which is either a Holstein or a Guernsey. The government of Bovinopolis wants to divide the greater metropolitan area into some number of contiguous districts, so that each district contains at most KK pastures (1≤K≤N1 \leq K \leq N), and every pasture is contained in exactly one district. Since the government is currently controlled by Holsteins, they want to find a way to redistrict which minimizes the number of Guernsey-majority or tied districts (a district is tied if the number of Guernseys equals the number of Holsteins). A concerned coalition of Guernseys is trying to figure out how much damage might be done by the government's redistricting. Help them figure out the worst-case minimum number of districts which are either Guernsey-majority or tied.

输入格式

The first line contains a two space-separated integers NN and KK. The second line contains a string of length NN. Each character is either 'H' or 'G', for Holstein or Guernsey.

输出格式

Please output the minimum possible number of districts that are Guernsey-majority or tied.

数据范围

(见题面原文)

样例

样例 1

7 2
HGHGGHG
3
Problem credits: Dhruv Rohatgi