SRM 670 Div2 Medium Drbalance

問題

plus/minus文字列とは'+'と'-'だけで構成された文字列のこと. ここで'+'の個数から'-'の個数を引いた数をスコアとする時. 与えられた文字列のプレフィックスのスコアが負となる場合の数を考える. この数が高々kになるように文字列を'-'から'+'に編集する時, 最小の編集回数を求める問題.

解答

  • できるだけ多くのprefixでスコアを高くしたい.
  • prefix集合を考えるので,最左の'-'を'+'に編集するのが最適な選択となる.
  • そのように編集していき,条件に合致する最小の編集回数を求める.
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;
    }
};