Nbrevu

Tuenti Contest 7 (Pablo Moreno)

Jun 20th, 2011
1,174
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×