SRM 528 Div2 Easy

問題

'o', 'x', '?'が含まれた文字列が与えられ,'?'を'o', 'x'に変えて回文を作る.'o'を変えるのにoCost, 'x'に変えるのにxCostが必要.回文を作るときの最小コストを求めよ

解答

s[i] = s[n-i-1] = '?'の時コストの小さい方に変える.
それだけ

class MinCostPalindrome
{
public:
  int getMinimum(string s, int oCost, int xCost)
    {
      int i,j;
      int n = s.size();
      int ret = 0;
      for(i = 0; i < n/2; i++){
        if (s[i] == '?'){
          if (s[n-i-1] == '?') ret += 2 * min(oCost, xCost);
          else if (s[n-i-1] == 'o') ret += oCost;
          else ret += xCost;
        }else {
          if (s[n-i-1] == '?'){
            if (s[i] == 'o') ret += oCost;
            else ret += xCost;
          }else if (s[n-i-1] != s[i]) return -1;
        }
      }
      return ret;
    }
};