URAL1031[Railway tickets]

动态规划。朴素的O(n^2)的应该不能过。所以要优化成线性的。


如果要花C1的钱来转移,当然要尽量靠前而又不要超过L1的距离,其他同理。所以分别转移。我用了一个双端队列。具体看代码吧。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-20


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <set>


using std::set;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


class Application


{


      static const int oo=1000000000;


      int L1,L2,L3;


      int C1,C2,C3;


      int N;


      int start,end;


      vector<int> d;


      int price(int f,int t)


      {


          if (d[t]-d[f]<=L1) return C1;


          if (d[t]-d[f]<=L2) return C2;


          if (d[t]-d[f]<=L3) return C3;


          return oo;


      }


      public:


      Application()


      {


                    cin>>L1>>L2>>L3


                       >>C1>>C2>>C3


                       >>N


                       >>start>>end;


                    if (start>end)


                    {


                       int swap=start;


                       start=end;


                       end=swap;


                    }


                    start–;


                    end–;


                    d.resize(N);


                    d[0]=0;


                    for (int i=1;i<N;i++)


                        cin>>d[i];


      }


      int run()


      {


          vector<int> f(N);


          std::deque<int> q1,q2,q3;


          f[start]=0;


          q1.push_back(start);


          q2.push_back(start);


          q3.push_back(start);


          for (int i=start+1;i<=end;i++)


          {


              f[i]=oo;


              while ((!q1.empty())&&(d[i]-d[q1.front()]>L1)) q1.pop_front();


              while ((!q2.empty())&&(d[i]-d[q2.front()]>L2)) q2.pop_front();


              while ((!q3.empty())&&(d[i]-d[q3.front()]>L3)) q3.pop_front();


              if ((!q1.empty())&&(f[i]>f[q1.front()]+price(q1.front(),i)))


                 f[i]=f[q1.front()]+price(q1.front(),i);


              if ((!q2.empty())&&(f[i]>f[q2.front()]+price(q2.front(),i)))


                 f[i]=f[q2.front()]+price(q2.front(),i);


              if ((!q3.empty())&&(f[i]>f[q3.front()]+price(q3.front(),i)))


                 f[i]=f[q3.front()]+price(q3.front(),i);


              q1.push_back(i);


              q2.push_back(i);


              q3.push_back(i);


          }


          cout<<f[end]<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}