hi all
im having a probe creating this algorithm:
i need to create a dynamic algorithm, the one below the greedy one, to formate text. everything i need is here but i cant figure out how to compute the line_cost and store it into an array
any ideas?
thanx



Code:
#include <iostream>
#include <vector>
#include <string>

//////////////////////////////////////////////////////
///
///  Usage:
///
///    format_text text_width
///
///  reads lines of text on standard input, then
///  prints the text, formatted, on standard output.
///
///  line breaking is done to minimize a penalty
function.
///
//////////////////////////////////////////////////////

#include "sprint.h"

using std::vector;
using std::map;
using std::string;

using std::cout;
using std::cerr;
using std::cin;
using std::endl;

#define DEFAULT_TEXT_WIDTH 60
#define INT_INFINITY (1<<30)

#define MIN(a,b) ((a)<(b)?(a):(b))

// trim trailing blanks from a given string
void
trim(string& s) {
  int i = s.size()-1;  
  while (i >= 0 && s[i] == ' ')
    --i;
  s.erase(i+1);
}

// return the penalty associated with a given line
int line_cost(string line, int text_width) {
  trim(line);
  int gap = text_width - line.size();
  if (gap < 0) return 1000000;
  return gap*gap*gap;
}

//
// given a sequence of n words, and integer text_width
//
// find the minimum total penalty possible for 
// any formatting of words[0], words[1], ...,words[n-1]
//
// return the formatted text as a string
//

string format_paragraph( vector<string> words, int
text_width) {


//this is the greedy algorithm

 /*string output = "";

  int length=0;

  for (int i=0;  i < words.size(); ++i) {
    if (length > 0 && length + words[i].size() >
text_width) {
      output += "\n";
      length = 0;
    }
    output += words[i] + " ";
    length += words[i].size() + 1;
  }
  if (length > 0) output += "\n";
  return output;*/
  


// this is the dynamic algorithm

  int last = (int)words.size()-1;
  for(int i=last; i>=0;i--){}
   
    
}    
    

int main(int argc, char *argv[]) {

  int text_width = DEFAULT_TEXT_WIDTH;

  if (argc >= 2) {
    text_width = atoi(argv[1]);
  }

  // read, format, and output a sequence of paragraphs
  // (new paragraph starts with a word "<p>")

  while (std::cin) {

    // get paragraph
    vector<string> words;
    while (std::cin) {
      string word;
      std::cin >> word;
      if (word.empty()) break;
      if (word == "<p>") break;
      words.push_back(word);
    }

    // output paragraph, formatted
    if (words.empty()) continue;
    cout << format_paragraph(words, text_width);
    cout << endl;
  }
}