Poj Solution 1093

http://poj.org/problem?id=1093

#include<iostream>
using namespace std;

const char space=' ';
char word[10001],l;
int len[10002],m,n;
int jie[10002];
int chen[10002];
long bad[10002];

void init()
{int h=0,j=1,t=0;
    
    while(cin.get())
    {if(cin.peek()==10)break;
    
    while(cin.peek()!=10)
    {if(cin.peek()==32){cin.get();if(t){len[j++]=t;t=0;}}
        else {cin.get(word[h++]);
            t++;}
    }
    if(t){len[j++]=t;t=0;}
    }
len[0]=0;
m=j-1;    
l=h;
//for(i=0;i<l;i++)cout<<word[i];
//cout<<endl;
//for(i=1;i<=m;i++)cout<<len[i]<<endl;
}

long point(long n,long p)
{long j=p/n,s=0;
while(p%n)
{s+=(j+1)*(j+1);
p-=j+1;n--;    
}
return s+(p/n)*(p/n)*n;
}


void doit()
{long s,p,j,i;
 jie[0]=0;bad[0]=0;
 jie[1]=1;bad[1]=500;
 chen[0]=0;chen[1]=1;    
 for(i=2;i<=m;i++)
 {bad[i]=500+bad[i-1];jie[i]=i;chen[i]=chen[i-1]+1; 
  s=len[i]+1+len[i-1];
 
  for(j=i-1;s<=n&&j>0;j--)
     {p=point(i-j,n-s)+bad[j-1];
     if(p<bad[i]||(p==bad[i]&&chen[j-1]<chen[jie[i]-1])){bad[i]=p;jie[i]=j;chen[i]=chen[j-1]+1;}
     
    if(j>1)s+=len[j-1]+1;
     }
 }
}
void print()
{int stack[10001],i,j,s,h;

for(i=m;i>0;i=jie[i]-1)
{s=0;
 for(j=i;j>=jie[i];j--)
 s+=len[j];s=n-s;

 for(j=jie[i];j<i;j++)
    {stack[j]=s/(i-j);s-=s/(i-j);}
 stack[i]=-1;
}
stack[0]=-1;
h=0;
for(i=1;i<=m;i++)
{for(j=0;j<len[i];j++)cout<<word[h++];
//if(stack[i]==-1&&stack[i-1]==-1){for(j=0;j<n-len[i];j++)cout<<space;cout<<endl;}
 if(stack[i]==-1)cout<<endl;
else for(j=0;j<stack[i];j++)cout<<space;
}
}

int main()
{while(1)
{cin>>n;if(n==0)break;
 init();
 doit();
 print();
 cout<<endl;
}
return 0;
}