以下是问题的实现:
- #include
- #include
- using namespace std;
- #define M 85 //每行最多M个字符
- #define N 49 //N个单词的输入序列
- #define INFINITE (M*M*M) //定义无穷大为M的立方,各个lc永远无法取到该值
- int l[N+1];//各个单词的字符数目
- int c[N+1];//问题的解
- int r[N+1];//存放最优解,k值
- unsigned int lc[N+1][N+1];//lc[i][j]是第i个单词到第j个单词的额外空格符数量的立方
- void print_neatly();//求解整齐打印
- void cal_lc();//计算lc值
- int give_line(int j);//打印最优解
- void main(int argc, char **argv){
- cout<<><>< li=""><><>
- ifstream infile;
- infile.open("input.txt");//读入一个有各点坐标的文档
- if (!infile)
- {
- cout<<"error!"<<>< li=""><>
- }
- int i=1;
- while (infile>>l[i])
- {
- i++;
- }
- for (int j=1;j<=N;j++)
- {
- cout<<><>< li=""><><>
- if (j==0)
- {
- cout<<>< li=""><>
- }
- }
- cout<<>< li=""><>
- print_neatly();
- give_line(N);
- cout<<"所有行的(除最后一行外)额外空格数的立方之和为:"<<><>< li=""><><>
- }
- void print_neatly(){
- c[0] = 0;
- cal_lc();
- for (int j=1;j<=N;j++)
- {
- c[j]= c[0]+lc[1][j];//先取c[j]的初值是k=1时的值
- r[j]=1;
- for (int k=1;k<=j;k++)
- {
- int q=c[k-1]+lc[k][j];
- if (q<>< li=""><>
- {
- c[j]= q;
- r[j]=k;
- }
- }
- }
- }
- void cal_lc(){//计算lc值
- for (int i=1;i<=N;i++)
- {
- for (int j=i;j<=N;j++)
- {
- int words_length=0;
- for (int k=i;k<=j;k++)
- {
- words_length += l[k];
- }
- int extra=M-j+i-words_length;
- if (extra<0)
- {
- lc[i][j] = INFINITE;
- }else if(j==N && extra>=0){
- lc[i][j]=0;
- }else{
- lc[i][j]= extra*extra*extra;
- }
- }
- }
- }
- int give_line(int j){
- int i=r[j],k;//k是划分后的行数
- if (i==1)
- {
- k=1;
- }else{
- k=give_line(i-1)+1;
- }
- cout<<"行号\t起始单词\t结束单词"<<>< li=""><>
- cout<<><><><><><>< li=""><><><><><><>
- return k;
- }
输入文件input.txt如下:
4 2 4 7 2 6 2 2 3 11
4 7 9 4 2 3 10 8 2 13
3 7 11 4 2 5 1 7 8 13
13 8 12 8 7 4 6 2 3 7 11
3 13 3 7 2 11 10 8
注意以上数据是根据某英文书籍某段话的统计,包括代码中的M值,N值。
运行结果:
整齐打印的结果是:
Just as each project is unique so is its environment This chapter discusses someXXXXX
of the components involved in understanding the project environment such as using aXX
systems approach understanding organizations managing stakeholders matching productXX
life cycles to the project environment and understanding the context of informationXX
technology procjects
第一行额外空格数是5,第二到第四的额外空格数为2,所以53+23+23+23=149。
本文出自 “我的主场” 博客,请务必保留此出处http://1439154.blog.51cto.com/1429154/1190038
联系客服