/********************************************************************
 University of Toronto                      Computer Science CSC B70S
 Scarborough Campus                              Monday 22 March 1999
              Homework Assignment 4: Dynamic Programming
 ********************************************************************/
//////////////////////////////////////////////////////////////////////
//         Last name: 
//        First name: 
//    Student number: 
//          Username: 
//  Tutorial section: 
//////////////////////////////////////////////////////////////////////

//  ****  FILL OUT THE IDENTIFICATION SECTION ABOVE AND MAKE  ****  //
//  ****    APPROPRIATE CHANGES AND ADDITIONS TO THIS FILE    ****  //

/********************************************************************
 **  FILE:  dp.cc                                                  **
 ********************************************************************
 **  Complete program to solve the "array merge" problem using     **
 **  dynamic programming techniques.                               **
 ********************************************************************/


/* -------------------- Header file inclusions. ------------------- */

#include <assert.h>
#include <iostream.h>


/* ---------------- Symbolic constant definitions. ---------------- */



/* -------------- Function declarations (prototypes). ------------- */



/* ---------------- Definition of `main' function. ---------------- */

//
// FUNCTION: main()
//
// Solves the "array merge" problem using dynamic programming.  The
// program starts by inputting the number of segments to merge and
// their sizes.  Then, appropriate functions are called to solve the
// problem and the results are outputted to the screen.
//
// PARAMETERS:
//    (NONE: command-line arguments not used for this program)
//
// Preconditions:
//    The values entered by the user are nonnegative integers.
//
// RETURN VALUE:
//    int   exit status ( 0 = OK )
//
// Postconditions:
//    The solution to the problem is outputted to the screen.
//
// OUTPUT FORMAT:
//    The minimum cost for the merge should be printed as an integer,
//    and the optimal sequence of merge operations should be printed
//    in the format used on the assignment handout, using "+" to
//    indicate merges, and properly balanced parentheses.  For the
//    example given on the first page of the assignment handout, the
//    output should look like this:
//
//        Minimum cost of performing the merge: 32
//
//        Optimal sequence of merge operations: 
//        ( S_0 + ( ( S_1 + S_2 ) + S_3 ) )
//
//    (since this is in C++, indices start at 0 instead of 1).  Note
//    that each segment number should be preceded with the string "S_"
//    (with *no* whitespace between "S_" and the segment number) and
//    that you should *not* use any other symbols in your output.
//
int main()
{
   int  num_segments;   // number of segments
   int *segment_size;   // array of segment sizes

   // Input the number of segments.
   cout << "Enter the number of segments: ";
   cin >> num_segments;
   assert( num_segments >= 0 );
   cout << endl;

   // Allocate memory for the array of segment sizes.
   assert( segment_size = new int[ num_segments ] );

   // Input the array of segment sizes.
   for ( int i = 0; i < num_segments; i++ ) {
      cout << "   Enter the size of segment number " << i << ": ";
      cin >> segment_size[i];
      assert( segment_size[i] >= 0 );
   } //end for
   cout << endl;

   // Compute the solution.

   // *** REMOVE THIS COMMENT AND ADD APPROPRIATE CODE HERE! *** //

   // Output the minimum cost.
   cout << "Minimum cost of performing the merge: ";

   // *** REMOVE THIS COMMENT AND ADD APPROPRIATE CODE HERE! *** //

   // Output the sequence of merges.
   cout << "Optimal sequence of merge operations: ";

   // *** REMOVE THIS COMMENT AND ADD APPROPRIATE CODE HERE! *** //

   // Free the memory used by the array of segment sizes.
   delete[] segment_size;

   return 0;
} //end main()


/* ---------------- Definitions of other functions. --------------- */

   // *** REMOVE THIS COMMENT AND ADD APPROPRIATE CODE HERE! *** //