题意：输入一段短文（所有字符总数不超过10000），要求格式化成两端对齐（每行长度为n，1 <= n <= 80）的方式输出并使得总坏值最小（一个空隙的坏值是这个空隙的空格总数减1后的平方），若有多种方案输出空格数字典序最小方案。
题目链接：http://poj.org/problem?id=1093
——>>状态：dp[i]表示从第i个单词开始到最后一个单词的最小总坏值（第i个单词是这一行的第1个单词）
状态转移方程：dp[i] = min(dp[i], dp[j + 1] + Badness(i, j));（Badness(i, j)表示第i个单词到第j个单词放在一行的最小总坏值，贪心一下，空格平均的时候最小。。）
如果一行只有一个单词，那么输出这个单词后，后面要不要补空格呢？答案：poj 1093补与不补都可以AC，而在zoj 1147不能补。。
想想，这个程序可以给自已用来做文本对齐呢。。好题。。实用。。
#include <cstdio>
#include <cstring>const int MAXL = 80 + 10;
const int MAXN = 10000 + 10;char szLine[MAXN];
char szWord[MAXN][MAXL];
int n;
int nWordCnt;
int dp[MAXN];
int nLastTo[MAXN];
int nSum[MAXN];void Read()
{getchar();nWordCnt = 0;while (gets(szLine)){if (szLine[0] == '\0') break;sscanf(szLine, "%s", szWord[++nWordCnt]);for (int i = 0; szLine[i] != '\0'; ++i){if (szLine[i] == ' '){while (szLine[i] == ' '){i++;}sscanf(szLine + i, "%s", szWord[++nWordCnt]);}}}
}void Init()
{nSum[0] = 0;for (int i = 1; i <= nWordCnt; ++i){nSum[i] = nSum[i - 1] + strlen(szWord[i]);}
}int Sum(int i, int j)
{return nSum[j] - nSum[i - 1];
}int LeastLen(int i, int j)
{return Sum(i, j) + j - i;
}int Badness(int i, int j)
{if (i == j){return 500;}int nBlankCnt = n - Sum(i, j);int nGapCnt = j - i;int nGapLen = nBlankCnt / nGapCnt;int nRemain = nBlankCnt % nGapCnt;return (nGapLen - 1) * (nGapLen - 1) * (nGapCnt - nRemain) + nGapLen * nGapLen * nRemain;
}void Dp()
{memset(dp, 0x3f, sizeof(dp));dp[nWordCnt + 1] = 0;for (int i = nWordCnt; i >= 1; --i){for (int j = i; j <= nWordCnt && LeastLen(i, j) <= n; ++j){if (dp[j + 1] + Badness(i, j) <= dp[i]){dp[i] = dp[j + 1] + Badness(i, j);nLastTo[i] = j;}}}
}void PrintBlank(int nNum)
{for (int i = 0; i < nNum; ++i){putchar(' ');}
}void Output()
{int nL = 1;while (true){int nR = nLastTo[nL];if (nL == nR){puts(szWord[nL]);}else{int nBlankCnt = n - Sum(nL, nR);int nGapCnt = nR - nL;int nGapLen = nBlankCnt / nGapCnt;int nRemain = nBlankCnt % nGapCnt;printf("%s", szWord[nL]);for (int i = 0; i < nGapCnt - nRemain; ++i){PrintBlank(nGapLen);printf("%s", szWord[nL + 1 + i]);}for (int i = 0; i < nRemain; ++i){PrintBlank(nGapLen + 1);printf("%s", szWord[nR - nRemain + 1 + i]);}puts("");}if (nR == nWordCnt) break;nL = nR + 1;}puts("");
}int main()
{while (scanf("%d", &n) == 1 && n){Read();Init();Dp();Output();}return 0;
}