// Hotel to shuttle using dynamic programming.
// Similar to CLRS assembly-line scheduling.

// Saves traceback explicitly.

#include <stdio.h>

int ud[7]={0,9,9,3,4,8,7};
int ld[7]={0,12,5,6,4,5,9};
int ul[7]={0,2,3,1,3,4,999};
int lu[7]={0,2,1,2,2,1,999};

int u[7],l[7];
char uTrace[7],lTrace[7];

int main()
{
int i;
char uORl;

// Start at hotel at no cost.
u[0]=0;
l[0]=0;
uTrace[0]='x';
lTrace[0]='x';

for (i=1;i<=6;i++)
{
  // Cost for next upper corner
  if (u[i-1]+ud[i]<=l[i-1]+ld[i]+lu[i])
  {
    // Arrive here from east
    u[i]=u[i-1]+ud[i];
    uTrace[i]='c';
  }
  else
  {
    // Arrive here from south
    u[i]=l[i-1]+ld[i]+lu[i];
    uTrace[i]='s';
  }

  // Cost for next lower corner
  if (l[i-1]+ld[i]<=u[i-1]+ud[i]+ul[i])
  {
    // Arrive here from east
    l[i]=l[i-1]+ld[i];
    lTrace[i]='c';
  }
  else
  {
    // Arrive here from north
    l[i]=u[i-1]+ud[i]+ul[i];
    lTrace[i]='s';
  }
}

printf("   ");
for (i=0;i<=6;i++)
  printf("  %3d  ",i);
printf("\n");
printf("U  ");
for (i=0;i<=6;i++)
  printf("%3d(%c) ",u[i],uTrace[i]);
printf("\n");
printf("L  ");
for (i=0;i<=6;i++)
  printf("%3d(%c) ",l[i],lTrace[i]);
printf("\n");

printf("Traceback:\n");
uORl='u';
for (i=6;i>0; )
  if (uORl=='u')
  {
    printf("u[%d] %d\n",i,u[i]);
    if (uTrace[i]=='s')
      uORl='l';
    else
      i--;
  }
  else
  {
    printf("l[%d] %d\n",i,l[i]);
    if (lTrace[i]=='s')
      uORl='u';
    else
      i--;
  }
}