daily pastebin goal
24%
SHARE
TWEET

Tuenti Contest 7 (Pablo Moreno)

Nbrevu Jun 20th, 2011 862 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top