SRM 670 Div2 Medium Drbalance

問題

SRM 670 - TopCoder Wiki

+と-からなる文字列を考える. ある文字列のスコアは+の数から-の数を引いた数で表される. 今,ある文字列のnegativityをその文字列のprefixの内,スコアが負になる数とする. ある文字列とkが与えられた時に,任意の位置の-を+に書き換え,negativityをk以下にする時, 最小の書き換え回数を求める問題.

解答

  • 最小の回数でnegativityを下げる最適な戦略は最左の-を+に書き換えること
  • negativityがk以下になるまで上記の操作を繰り返し,最小の操作回数を求める.
class Drbalance
{
public:
  int score(string & s) {
    int res = 0;
    for (int i = 0; i < s.size(); i++) {
      int score = 0;
      for (int j = 0; j < s.size()-i;j++){
        if (s[j] == '+') score++;
        else score--;
      }
      if (score < 0)res++;
    }
    return res;
  }
  int lesscng(string s, int k)
    {
      string s2 = s;
      if (score(s) <= k)return 0;
      int res = 0;
      for (int i = 0; i < s.size(); i++){
        if (s[i] == '-') res++;
        s2[i] = '+';
        if (score(s2) <= k) return res;
      }
      return res;
    }
};