変な問題。
http://community.topcoder.com/stat?c=problem_statement&pm=14060
問題
-
- で構成された文字列のバランスとは、文字列中における( (+の数)-(-の数) )で計算できる。
文字列Sが与えられる。
Sのprefixのうち、バランスが負になるものをK個以下にしたい。
文字列Sの中身を+-反転できるとき、条件を満たすのに必要な最小反転数を求めよ。
解法
反転させるなら、先頭に近い方の-を+にする方がより多くのprefixがバランス負になることを防止できる。
よって「全prefixのうちバランスが負のものがK個以下かチェック」→「そうでないなら、先頭に近い-を+に反転」を繰り返せばよい。
class Drbalance { public: int lesscng(string s, int k) { int cnt=0; while(1) { int neg=0; int cur=0; FORR(r,s) { if(r=='+') cur++; else cur--; if(cur<0) neg++; } if(neg<=k) return cnt; cnt++; FORR(r,s) if(r=='-') { r='+'; break; } } } }
まとめ
なんとなくcorrect bracket sequenceを意識した問題?