最低限度の回文と喫茶店のコーヒー(Topcoder SRM 528 div2 250pt)

回文は英語でpalindromeと言うらしい。

photo by nodoca

　TopCoder Statistics - Problem Statement

　問題：文字数が偶数である文字列sが与えられる。sを構成する文字は'o','x','?'のいずれかである。あなたのタスクは'?'を文字列sが回文になるように'o'か'x'に置き換えることである。このとき置き換える際のコスト、oCostとxCostが整数として与えられるとして、最小のコストを返せ。回文にならないときは-1を返せ。

　例："oxo?xox?"　oCost:3　xCost:5　Returns: 8
　　　"ooooxxxx"　oCost:12 xCost:34 Returns: -1

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 class MinCostPalindrome{
	public:
	int getMinimum(string s, int oCost, int xCost)	{
        string a("i");
        string b("j");
        int mincost=0;
        printf("oCost=%d:xCost=%d\n",oCost,xCost);
        for(int i=0;i<s.size()/2;i++){
            a=s[i];b=s[s.size()-i-1];
            cout << a <<":"<< b <<":"<< i <<endl;
            if (a=="?" || b=="?"){
                if (a=="?" && b=="?") {
                    mincost+=2*min(oCost,xCost);
                }else{
                    if (a=="?") mincost+=(b =="o")? oCost:xCost;
                    if (b=="?") mincost+=(a =="o")? oCost:xCost;
                }
            }else{
                if (a!=b) {printf("not\n");return -1;}
            }
        }
        printf("mincost=%d\n",mincost);
        return mincost;
    }
};

int main(){
    MinCostPalindrome ob1;
    string string("ooooxxxx");
    int oc=3,xc=10;
    ob1.getMinimum(string,oc,xc);
    return 0;
}