elevator.c

/*	elevator.c

	Elevator stop optimization via dynamic programming.

	by: Steven Skiena
	begun: April 1, 2002
*/


/*
Copyright 2003 by Steven S. Skiena; all rights reserved. 

Permission is granted for use in non-commerical applications
provided this copyright notice remains intact and unchanged.

This program appears in my book:

"Programming Challenges: The Programming Contest Training Manual"
by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003.

See our website www.programming-challenges.com for additional information.

This book can be ordered from Amazon.com at

http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/

*/

#include <stdio.h>

#define	NFLOORS     25  /* the height of the building in floors */
#define MAX_RIDERS  50  /* what is the capacity of the elevator? */
#define MAXINT      100007

int stops[MAX_RIDERS];  /* what floor does everyone get off at? */
int nriders;            /* number of riders */
int nstops;             /* number of allowable stops */

int m[NFLOORS+1][MAX_RIDERS];   /* dynamic programming cost table */
int p[NFLOORS+1][MAX_RIDERS];   /* dynamic programming parent table */

int min(int a, int b) {
	if (a < b) {
        return(a); 
    }
    return(b);
}

int floors_walked(int previous, int current) {
    int nsteps=0;   /* total distance traveled */
    int i;          /* counter */

    for (i = 1; i <= nriders; i++) {
        if ((stops[i] > previous) && (stops[i] <= current)) {
            nsteps += min(stops[i]-previous, current-stops[i]);
        }
    }

    return(nsteps);
}

/*	m[i][j] denotes the cost of serving all the riders using j stops,
	the last of which is at floor i.  Zero is the originating floor.
*/

int optimize_floors() {
    int i, j, k;    /* counters */
    int cost;       /* costs placeholder */
    int laststop;   /* the elevator's last stop */

    for (i = 0; i <= NFLOORS; i++) {
        m[i][0] = floors_walked(0, MAXINT);
        p[i][0] = -1;
    }

    for (j = 1; j <= nstops; j++) { 
        for (i = 0; i <= NFLOORS; i++) {
            m[i][j] = MAXINT;
            for (k = 0; k <= i; k++) {
                cost = m[k][j-1] - floors_walked(k, MAXINT) +
                floors_walked(k, i) + floors_walked(i, MAXINT);
                if (cost < m[i][j]) {
                    m[i][j] = cost;
                    p[i][j] = k;
                }    
            }
        }
    }

    laststop = 0;
    for (i = 1; i <= NFLOORS; i++) { 
        if (m[i][nstops] < m[laststop][nstops]) {
            laststop = i;
        }
    }

    return(laststop);
}


void reconstruct_path(int lastfloor, int stops_to_go) {
    if (stops_to_go > 1) {
        reconstruct_path(p[lastfloor][stops_to_go], stops_to_go-1);
    }

    printf("%d\n", lastfloor);
}

void print_matrix(int m[NFLOORS+1][MAX_RIDERS]) {
    int i, j;    /* counters */

    for (j = 0; j <= nstops; j++) {
        for (i = 0; i <= NFLOORS; i++) {
            printf("%3d", m[i][j]);
        }
        printf("\n");
    }
}

int main(void) {
    int i, j;    /* counters */
    int laststop;

    scanf("%d %d", &nriders, &nstops);

    for (i = 1; i <= nriders; i++) {
        scanf("%d", &(stops[i]));
    }

    for (i = 1; i <= nriders; i++) {
        printf("%d\n", stops[i]);
    }

    laststop = optimize_floors();

    print_matrix(m);
    printf("\n");
    print_matrix(p);

    printf("cost = %d\n", m[laststop][nstops]);

    reconstruct_path(laststop, nstops);

    return 0;
}