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

// Traceback is determined implicitly.

#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];

int main()
{
int i;
char uORl;

// Start at hotel at no cost.
u[0]=0;
l[0]=0;

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];
  }
  else
  {
    // Arrive here from south
    u[i]=l[i-1]+ld[i]+lu[i];
  }

  // 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];
  }
  else
  {
    // Arrive here from north
    l[i]=u[i-1]+ud[i]+ul[i];
  }
}

printf("   ");
for (i=0;i<=6;i++)
  printf("  %3d  ",i);
printf("\n");
printf("U  ");
for (i=0;i<=6;i++)
  if (i==0)
    printf("%3d(x) ",u[i]);
  else if (u[i]==u[i-1]+ud[i])
    printf("%3d(c) ",u[i]);
  else
    printf("%3d(s) ",u[i]);
printf("\n");
printf("L  ");
for (i=0;i<=6;i++)
  if (i==0)
    printf("%3d(x) ",l[i]);
  else if (l[i]==l[i-1]+ld[i])
    printf("%3d(c) ",l[i]);
  else
    printf("%3d(s) ",l[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 (u[i]!=u[i-1]+ud[i])
      uORl='l';
    else
      i--;
  }
  else
  {
    printf("l[%d] %d\n",i,l[i]);
    if (l[i]!=l[i-1]+ld[i])
      uORl='u';
    else
      i--;
  }
}