Advertisement
Guest User

Untitled

a guest
Apr 14th, 2013
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. #define DEBUG 1
  6.  
  7. using namespace std;
  8.  
  9. vector<int> his;
  10. set<int> kis;
  11.  
  12. //Cache array for holding the min amount of times to refuel
  13. //for at i km.
  14. int D[1001];
  15.  
  16. // The count minimum refuels for km
  17. int S(int km) {
  18.     if(DEBUG) cout << "S("<<km<<")"<<endl;
  19.     int minimumRefuels=1000;    
  20.    
  21.     if(km==0)
  22.         return 1;
  23.     if(km<0)
  24.         return 1001;
  25.    
  26.     //Get minimum number of refuels over all branches
  27.     for(set<int>::const_iterator it = kis.begin(); it!=kis.end();it++) {
  28.        
  29.         //Has this been calculated before?
  30.         int tmp = km - *it;
  31.         if(tmp >0 && D[tmp]!=1001)
  32.             return D[tmp];
  33.        
  34.        
  35.  
  36.         minimumRefuels = std::min(minimumRefuels,S(tmp));
  37.     }  
  38.        
  39.     D[km] = minimumRefuels+1;
  40.     return D[km];
  41. }
  42. int main(int argc, const char * argv[])
  43. {
  44.  
  45.     his = vector<int>();
  46.     kis = set<int>();
  47.     int T=0;
  48.     int N=0;
  49.     cin >> T;
  50.     while(T-- >= 0) {
  51.         cin >> N;
  52.        
  53.         //Orders
  54.         int tmp=0;
  55.         for(int j=0; j<N;j++) {
  56.             cin >> tmp;
  57.             his.push_back(tmp);
  58.         }
  59.        
  60.         //Fuel tanks
  61.         for(int j=0;j<N;j++) {
  62.             cin >> tmp;
  63.             kis.insert(tmp);
  64.         }
  65.         if(DEBUG) {
  66.             set<int>::const_iterator it = kis.begin();
  67.             while(it != kis.end()) {
  68.                 cout << *it++ << endl;
  69.             }            
  70.         }
  71.        
  72.        
  73.         //Reset the cache array
  74.         for(int j=0;j<1001;j++) {
  75.             D[j] = 1001;
  76.         }
  77.        
  78.         //Process all orders
  79.         int minimumRefuels = 0;
  80.         for(int j=0; j<N;j++) {
  81.  
  82.             int minimumRoundRefuels = S(2*his[j]);
  83.             minimumRefuels += minimumRoundRefuels;
  84.  
  85.             if(DEBUG) { }
  86.             cout << "Min refuels for order " << j << " " << minimumRoundRefuels << endl;
  87.         }
  88.        
  89.         cout << minimumRefuels << endl;
  90.         kis.clear();
  91.         his.clear();
  92.     }
  93.    
  94.     return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement