Tuenti Contest 7 (Pablo Moreno)

/*
    Author: Pablo Moreno Olalla
    Email address: darthbrevu@yahoo.es
*/
#include <cstdio>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

//This problem seems like a good example for the A* algorithm. Unfortunately, it's very costly for large strings.
//I assume that costs are positive (otherwise, there may be no optimal cost).

class TileProblem   {
private:
    static string getAllChars(const string &in,const string &out)   {
        vector<char> buf(0);
        buf.reserve(in.size()+out.size()+1);
        for (string::const_iterator it=in.begin();it!=in.end();++it) if (find(buf.begin(),buf.end(),*it)==buf.end()) buf.push_back(*it);
        for (string::const_iterator it=out.begin();it!=out.end();++it) if (find(buf.begin(),buf.end(),*it)==buf.end()) buf.push_back(*it);
        buf.push_back('\0');
        return string(static_cast<char *>(&buf[0]));
    }
public:
    string in;
    string out;
    unsigned int addPrice,delPrice,swapPrice;
    const string allChars;
    unsigned int trueSwapPrice;
    TileProblem(const string &s1,const string &s2,unsigned int ap,unsigned int dp,unsigned int sp):in(s1),out(s2),addPrice(ap),delPrice(dp),swapPrice(sp),allChars(getAllChars(s1,s2))  {
        if (addPrice+delPrice<swapPrice) trueSwapPrice=addPrice+delPrice;
        else trueSwapPrice=swapPrice;
    }
};

unsigned int solve(const TileProblem &tp)   {
    size_t s1=tp.in.size();
    size_t s2=tp.out.size();
    vector<vector<unsigned int> > dynMatrix(s1+1,vector<unsigned int>(s2+1));
    size_t i,j;
    unsigned long ca,cd,cs;
    for (i=0;i<=s1;++i) dynMatrix[i][0]=i*tp.delPrice;
    for (j=1;j<=s2;++j) {
        dynMatrix[0][j]=j*tp.addPrice;
        for (i=1;i<=s1;++i) if (tp.in[i-1]==tp.out[j-1]) dynMatrix[i][j]=dynMatrix[i-1][j-1];
        else    {
            ca=tp.addPrice+dynMatrix[i][j-1];
            cd=tp.delPrice+dynMatrix[i-1][j];
            cs=tp.trueSwapPrice+dynMatrix[i-1][j-1];
            dynMatrix[i][j]=min(min(ca,cd),cs);
        }
    }
    return dynMatrix[s1][s2];
}

int main(int argc,char **argv)  {
    //The first two lines are not strictly necessary, but make the code a little more handy.
    if (argc>=2) freopen(argv[1],"r",stdin);
    if (argc>=3) freopen(argv[2],"w",stdout);
    string tmp;
    string s1,s2;
    unsigned int c1,c2,c3;
    locale l("es_ES.UTF-8");
    cin.imbue(l);
    do  {
        getline(cin,tmp);
        istringstream iss(tmp);
        iss>>s1>>s2;
        iss.ignore(1);
        iss>>c1;
        iss.ignore(1);
        iss>>c2;
        iss.ignore(1);
        iss>>c3;
        if (iss.fail()) break;
        if (s1==s2) cout<<0<<endl;
        cout<<solve(TileProblem(s1,s2,c1,c2,c3))<<endl;
    }   while (!cin.eof());
    return 0;
}