Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement