UVa 301 - Transportation

Accepted date: 2011-09-08
Ranking (as of 2013-08-03): 193 out of 1117
Language: C++

/*
  UVa 301 - Transportation

  To build using Visual Studio 2008:
    cl -EHsc -O2 transportation.cpp
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct order // ticket order
{
  int start; // starting station
  int destination; // destination station
  int nr_passengers; // number of passengers
  int earning; // earning if order is accepted
};

bool compare_order(const order& i, const order& j)
{
  return i.start < j.start;
}

enum order_state {unprocessed, accepted, rejected};

void accept_orders(int capacity, int last_station, int current_station,
  int next_order /* order index to be exmained */,
  int nr_orders, const vector<order>& orders,
  vector<order_state>& order_states, int earning, int& max_earning)
{
  // when arriving at the current station, recaluclate the capacity
  if (!next_order) {
    for (int i = 0; i < nr_orders; i++)
      if (orders[i].destination == current_station &&
        order_states[i] == accepted)
        // passengers get off at the current station
        capacity += orders[i].nr_passengers;
  }
  if (current_station == last_station) {
    if (earning > max_earning)
      max_earning = earning;
    return;
  }
  else {
    int remainig_earning = 0;
    for (int i = next_order; i < nr_orders; i++)
      if (orders[i].start >= current_station)
        remainig_earning += orders[i].earning;
    if (earning + remainig_earning <= max_earning)
      return;
  }

  // try to take the passengers on board
  bool processed = false;
  if (capacity > 0) {
    for (int i = next_order; i < nr_orders; i++)
      if (orders[i].start == current_station && order_states[i] == unprocessed) {
        processed = true;
        if (orders[i].nr_passengers <= capacity) {
          order_states[i] = accepted;
          accept_orders(capacity - orders[i].nr_passengers, last_station,
            current_station, i + 1, nr_orders, orders, order_states, 
            earning + orders[i].earning, max_earning);
        }
        order_states[i] = rejected;
        accept_orders(capacity, last_station, current_station, i + 1,
          nr_orders, orders, order_states, earning, max_earning);
        order_states[i] = unprocessed;
        break;
      }
  }
  if (!processed) // all of the orders for the current station has been processed
    accept_orders(capacity, last_station, current_station + 1, 0,
      nr_orders, orders, order_states, earning, max_earning);
}

int main()
{
  while (true) {
    int capacity, last_station, nr_orders;
    cin >> capacity >> last_station >> nr_orders;
    if (!capacity && !last_station && !nr_orders)
      break;
    vector<order> orders(nr_orders);
    for (int i = 0; i < nr_orders; i++) {
      cin >> orders[i].start >> orders[i].destination >>
        orders[i].nr_passengers;
      orders[i].earning = orders[i].nr_passengers *
        (orders[i].destination - orders[i].start);
    }
    sort(orders.begin(), orders.end(), compare_order);
      // sort the orders in ascending order of starting station
    int max_earning = -1;
    vector<order_state> order_states(nr_orders, unprocessed);
    accept_orders(capacity, last_station, 0, 0, nr_orders, orders, order_states,
      0, max_earning);
    cout << max_earning << endl;
  }
  return 0;

}