Nbrevu

Tuenti Contest 7 (Pablo Moreno)

Jun 20th, 2011
1,139
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Author: Pablo Moreno Olalla
  3.     Email address: darthbrevu@yahoo.es
  4. */
  5. #include <cstdio>
  6. #include <string>
  7. #include <vector>
  8. #include <sstream>
  9. #include <iostream>
  10. #include <algorithm>
  11.  
  12. using namespace std;
  13.  
  14. //This problem seems like a good example for the A* algorithm. Unfortunately, it's very costly for large strings.
  15. //I assume that costs are positive (otherwise, there may be no optimal cost).
  16.  
  17. class TileProblem   {
  18. private:
  19.     static string getAllChars(const string &in,const string &out)   {
  20.         vector<char> buf(0);
  21.         buf.reserve(in.size()+out.size()+1);
  22.         for (string::const_iterator it=in.begin();it!=in.end();++it) if (find(buf.begin(),buf.end(),*it)==buf.end()) buf.push_back(*it);
  23.         for (string::const_iterator it=out.begin();it!=out.end();++it) if (find(buf.begin(),buf.end(),*it)==buf.end()) buf.push_back(*it);
  24.         buf.push_back('\0');
  25.         return string(static_cast<char *>(&buf[0]));
  26.     }
  27. public:
  28.     string in;
  29.     string out;
  30.     unsigned int addPrice,delPrice,swapPrice;
  31.     const string allChars;
  32.     unsigned int trueSwapPrice;
  33.     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))  {
  34.         if (addPrice+delPrice<swapPrice) trueSwapPrice=addPrice+delPrice;
  35.         else trueSwapPrice=swapPrice;
  36.     }
  37. };
  38.  
  39. unsigned int solve(const TileProblem &tp)   {
  40.     size_t s1=tp.in.size();
  41.     size_t s2=tp.out.size();
  42.     vector<vector<unsigned int> > dynMatrix(s1+1,vector<unsigned int>(s2+1));
  43.     size_t i,j;
  44.     unsigned long ca,cd,cs;
  45.     for (i=0;i<=s1;++i) dynMatrix[i][0]=i*tp.delPrice;
  46.     for (j=1;j<=s2;++j) {
  47.         dynMatrix[0][j]=j*tp.addPrice;
  48.         for (i=1;i<=s1;++i) if (tp.in[i-1]==tp.out[j-1]) dynMatrix[i][j]=dynMatrix[i-1][j-1];
  49.         else    {
  50.             ca=tp.addPrice+dynMatrix[i][j-1];
  51.             cd=tp.delPrice+dynMatrix[i-1][j];
  52.             cs=tp.trueSwapPrice+dynMatrix[i-1][j-1];
  53.             dynMatrix[i][j]=min(min(ca,cd),cs);
  54.         }
  55.     }
  56.     return dynMatrix[s1][s2];
  57. }
  58.  
  59. int main(int argc,char **argv)  {
  60.     //The first two lines are not strictly necessary, but make the code a little more handy.
  61.     if (argc>=2) freopen(argv[1],"r",stdin);
  62.     if (argc>=3) freopen(argv[2],"w",stdout);
  63.     string tmp;
  64.     string s1,s2;
  65.     unsigned int c1,c2,c3;
  66.     locale l("es_ES.UTF-8");
  67.     cin.imbue(l);
  68.     do  {
  69.         getline(cin,tmp);
  70.         istringstream iss(tmp);
  71.         iss>>s1>>s2;
  72.         iss.ignore(1);
  73.         iss>>c1;
  74.         iss.ignore(1);
  75.         iss>>c2;
  76.         iss.ignore(1);
  77.         iss>>c3;
  78.         if (iss.fail()) break;
  79.         if (s1==s2) cout<<0<<endl;
  80.         cout<<solve(TileProblem(s1,s2,c1,c2,c3))<<endl;
  81.     }   while (!cin.eof());
  82.     return 0;
  83. }
RAW Paste Data