範例程式碼 uva709

//uva709
#include <iostream>
#include <string> 
using namespace std;

int main(){	
	int width;
	while(cin >> width && width){
		cin.ignore();
		
		string words[10050];
		int sumLength[10050];
		int dp[10050];
		int endWord[10050];
		
		string tmp;
		int wordCnt = 1;  // not use 0
		// read the paragraph
		while(getline(cin,tmp) && tmp.size() > 0){
			// split ( including a long space
			int begin = 0;
			int end = 0;
			while(end != -1){
				end = tmp.find(' ',begin);
				words[wordCnt] = tmp.substr(begin,end - begin);
				if(words[wordCnt].size() != 0) ++wordCnt;
				begin = end+1;
			}
		}
		
		// calculate the length after pick each word
		sumLength[0] = 0;
		for(int i = 1 ; i < wordCnt ; ++i)
			sumLength[i] = sumLength[i-1] + words[i].size();
		
		// dp from right to left
		dp[wordCnt] = 0;  // the dp initial state
		// calculate the best position to put each remaining word
		for(int i = wordCnt-1 ; i > 0 ; --i){  // i: curWord
			dp[i] = dp[i+1] + 500;  // penalty of one word occupying one line
			endWord[i] = i;         // start from words[i] ends at words[i]
			
			// try to pick in as more words as possible( ... �B are�Bareactually�Bareactuallyconsidering.) 
			for(int j=i+1 ; j < wordCnt ; ++j){
				if(sumLength[j] - sumLength[i-1] + j - i > width) break;  // can not be a row (no space for ' ')
				int totalSpace = width - (sumLength[j] - sumLength[i-1]); // total extra space to fill
				int avgSpace = totalSpace / (j-i);                        // (average) middle space after between i to j words
				int extraSpace = totalSpace - avgSpace*(j-i);             // number of extra space
				// penalty of one row:  (number of avgSpace)*(length of space)^2 + (number of extra space)*(length of extra space)^2
				// length of space = midAvgSpace - 1 (that is, if midAvgSpace = 4, then penalty is 3^2)
				// length of extra space = midAvgSpace
				int cost = (j-i-extraSpace)*(avgSpace-1)*(avgSpace-1) + (extraSpace)*avgSpace*avgSpace;
				if( dp[i] >= dp[j+1] + cost ){
					dp[i] = dp[j+1] + cost;
					endWord[i] = j;    // start from words[i] ends at words[j]
				}
			}
		}
		
		// print the paragraph
		int curWord = 1;
		while(curWord < wordCnt){
			if(endWord[curWord] > curWord){
				int i = curWord;
				int j = endWord[i]/* - 1*/;
				int totalSpace = width - (sumLength[j] - sumLength[i-1]);
				int avgSpace = totalSpace / (j-i);
				int extraSpace = totalSpace - avgSpace*(j-i);
				
				int count = 0;         // how many avgSpace have been printed
				cout << words[i];      // start from words[i] ends at words[j]
				for(int nextWord = i+1 ; nextWord <= j ; ++nextWord){
					// print "avgSpace" space
					for(int space = 0 ; space < avgSpace ; ++space)
						cout << " ";
					if(++count > (j-i-extraSpace))
						cout << " ";
					cout << words[nextWord];					
				}
				cout << endl;
			}else{
				// if the word occupies one whole line
				cout << words[curWord] << endl;
			}
			curWord = endWord[curWord] + 1;
		}
		cout << endl;
		
	}
	return 0;
}