Passion is like genius; a miracle.

Problem description is http://acm.uva.es/p/v100/10026.html

Seems like a zero-one-knapsack, but a little more twisted. It took lots of time not because the complexity of the given problem, but because of the STL chores. -_-;;

I’d better read STL book again.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define MAX_INTEGER_VALUE 99999

// Represents each job
class Job {
public:
    int time;
    int fine;
    int ID;

    Job() {}
    Job(int ID, int time, int fine):ID(ID), time(time), fine(fine) {} 
};

class JobTimeLess {
public:
    bool operator()(const Job &lhs, const Job &rhs) const {
        return lhs.time < rhs.time;
    }
};

class EqualID {
private:
    int ID;
public:
    EqualID(Job job) {
        ID = job.ID;
    }

    bool operator()(const Job &j) const {
        return j.ID == ID;
    }
};

class Stage {
public:
    vector<Job> remained;
    int totalFine;

    Job jobFinished;

    Stage():totalFine(MAX_INTEGER_VALUE) {}
    Stage::~Stage() {}
};

int totalTime() {
    return 3+1+2+5;
}

Stage getTimeZero() {

    Stage stage;
    stage.remained.push_back(Job(1,3,4));
    stage.remained.push_back(Job(2,1,1000));
    stage.remained.push_back(Job(3,2,2));
    stage.remained.push_back(Job(4,5,5));

    return stage;
}

void dumpStage(Stage &s) {

    cout << "Remained Jobs" << endl;
    vector<Job>::iterator i;
    for (i = s.remained.begin() ; i != s.remained.end() ; i++) 
        cout <<"ID: " << (*i).ID 
             << " Time: " << (*i).time 
             << " Fine: " << (*i).fine << endl;
}

int computeFine(Stage &stage, Job job) {
    
   int fine = 0;
   vector<Job>::iterator i;
   for (i = stage.remained.begin() ; i != stage.remained.end() ; i++) {
        fine += (*i).fine;
   }

   return stage.totalFine + fine * job.time;
}


inline bool isLowerCost(Stage &target, Stage &stage, Job &job) {

    int fine = computeFine(stage, job);
    if (target.totalFine > fine)
        return true;

    // lexicographical ordering consideration 
    else if (target.totalFine == fine && target.jobFinished.ID > job.ID) 
        return true;

    return false;
}

int main() {

    vector<Stage> stages(totalTime() + 1);
    stages[0] = getTimeZero();
    stages[0].totalFine=0;


    for (int timeIdx = 0 ; timeIdx < totalTime() ; timeIdx++) {
        
        vector<Job>::iterator i;
        Stage &stage = stages[timeIdx];
    
        cout << "Time:" << timeIdx << endl;
        cout << "Considering..." << endl;
        dumpStage(stage);

        for (i = stage.remained.begin() ; i != stage.remained.end() ; i++) {

            Job job = *i;
            Stage &target = stages[timeIdx + job.time];

            if (isLowerCost(target, stage, job)) {

                // Set finished job
                target.jobFinished = job;

                // New total fine
                target.totalFine = computeFine(stage, job);

                // Copying remained jobs,
                // excluding the job finished
                target.remained = vector<Job> (stage.remained);
                vector<Job>::iterator r = 
                    find_if(target.remained.begin(), 
                        target.remained.end(), 
                        EqualID(job));
                target.remained.erase(r, r+1);
            }
        }
    }

    int timeIdx = totalTime();

    cout << "Result" << endl;
    while(timeIdx > 0) {

        Stage stage = stages[timeIdx];
        cout << "Time: " << timeIdx << " Job: " << stage.jobFinished.ID << endl;
        timeIdx = timeIdx - stage.jobFinished.time;

    }

    return 0;
}

The answer is: 2 1 3 4