Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- #define DEBUG 1
- using namespace std;
- vector<int> his;
- set<int> kis;
- //Cache array for holding the min amount of times to refuel
- //for at i km.
- int D[1001];
- // The count minimum refuels for km
- int S(int km) {
- if(DEBUG) cout << "S("<<km<<")"<<endl;
- int minimumRefuels=1000;
- if(km==0)
- return 1;
- if(km<0)
- return 1001;
- //Get minimum number of refuels over all branches
- for(set<int>::const_iterator it = kis.begin(); it!=kis.end();it++) {
- //Has this been calculated before?
- int tmp = km - *it;
- if(tmp >0 && D[tmp]!=1001)
- return D[tmp];
- minimumRefuels = std::min(minimumRefuels,S(tmp));
- }
- D[km] = minimumRefuels+1;
- return D[km];
- }
- int main(int argc, const char * argv[])
- {
- his = vector<int>();
- kis = set<int>();
- int T=0;
- int N=0;
- cin >> T;
- while(T-- >= 0) {
- cin >> N;
- //Orders
- int tmp=0;
- for(int j=0; j<N;j++) {
- cin >> tmp;
- his.push_back(tmp);
- }
- //Fuel tanks
- for(int j=0;j<N;j++) {
- cin >> tmp;
- kis.insert(tmp);
- }
- if(DEBUG) {
- set<int>::const_iterator it = kis.begin();
- while(it != kis.end()) {
- cout << *it++ << endl;
- }
- }
- //Reset the cache array
- for(int j=0;j<1001;j++) {
- D[j] = 1001;
- }
- //Process all orders
- int minimumRefuels = 0;
- for(int j=0; j<N;j++) {
- int minimumRoundRefuels = S(2*his[j]);
- minimumRefuels += minimumRoundRefuels;
- if(DEBUG) { }
- cout << "Min refuels for order " << j << " " << minimumRoundRefuels << endl;
- }
- cout << minimumRefuels << endl;
- kis.clear();
- his.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement