用C ++快速又脏
#include <sstream>#include <iostream>#include <vector>#include <cstdlib>#include <memory.h>using namespace std;int cac[1000][1000];string res[1000][1000];vector<string> words;int M;int go(int a, int b){ if(cac[a][b]>= 0) return cac[a][b]; if(a == b) return 0; int csum = -1; for(int i=a; i<b; ++i){ csum += words[i].size() + 1; } if(csum <= M || a == b-1){ string sep = ""; for(int i=a; i<b; ++i){ res[a][b].append(sep); res[a][b].append(words[i]); sep = " "; } return cac[a][b] = (M-csum)*(M-csum); } int ret = 1000000000; int best_sp = -1; for(int sp=a+1; sp<b; ++sp){ int cur = go(a, sp) + go(sp,b); if(cur <= ret){ ret = cur; best_sp = sp; } } res[a][b] = res[a][best_sp] + "n" + res[best_sp][b]; return cac[a][b] = ret;}int main(int argc, char ** argv){ memset(cac, -1, sizeof(cac)); M = atoi(argv[1]); string word; while(cin >> word) words.push_back(word); go(0, words.size()); cout << res[0][words.size()] << endl;}测试：
$ echo "The quick brown fox jumps over a lazy dog" |./a.out 10The quickbrown foxjumps overa lazy dog
编辑：只是在Wikipedia页面上查看了最低程度的衣衫wrap的自动换行。将算法更改为给定算法（惩罚为平方）
