Source Code

Problem: 1093  User: yzhw9981 
Memory: 1392K  Time: 79MS 
Language: C++  Result: Accepted 

Source Code 
# include <iostream>
# include <cstdlib>
using namespace std;
# include <vector>
# include <string>
# include <cstring>
class point
{
public:
   string str;
   int maxnum;
   vector<int> price;
   vector<int> left;
   point()
   {
   }
   point(char *p)
   {
	   str=string(p);
   }
};
int len;
int refer[1000][80],pre[1000][80][2];
vector<point> data;
int deal(int left,int pass)
{
	if(refer[left][pass]) return refer[left][pass];
	else if(left-pass+1==0) return data[left].price[pass-1];
	else
	{
		int res=999999999;
		for(int i=1;i<=data[left-pass].maxnum;i++)
		{
			if(deal(left-pass,i)+data[left].price[pass-1]<res) 
				res=deal(left-pass,i)+data[left].price[pass-1],pre[left][pass][0]=left-pass,pre[left][pass][1]=i;	
		}
		refer[left][pass]=res;
		return res;
	}
}
int cal(int space,int left)
{
	int *temp=new int[left];
	for(int i=1;i<left;i++) temp[i]=0;
	while(space)
	{
		for(int i=left-1;i>=1&&space;i--) temp[i]++,space--;
	}
	int total=0;
	for(int i=1;i<left;i++) total+=temp[i]*temp[i];
	delete[] temp;
	return total;
}
void init()
{
	for(int i=data.size()-1;i>=0;i--)
	{
		if(i==0)
		{
			data[i].maxnum=1;
			data[i].left.push_back(0);
			if(data[0].str.length()==len) data[i].price.push_back(0);
			else data[i].price.push_back(500);
		}
		else
		{
			int total=0;
			data[i].maxnum=1;
			total+=data[i].str.length();
			if(data[i].str.length()==len) data[i].price.push_back(0);
			else data[i].price.push_back(500);
			data[i].left.push_back(0);
			int p=i-1;
			while(p>=0&&total+data[p].str.length()+1<=len)
			{
				data[i].maxnum++;
				total+=data[p].str.length()+1;
				data[i].price.push_back(cal(len-total,data[i].maxnum));
				data[i].left.push_back(len-total);
				p--;
			}
		}

	}
}
void print(int left,int pass)
{
	if(pre[left][pass][1]) print(pre[left][pass][0],pre[left][pass][1]);
	int space1,space2;
	if(pass!=1)
	{
		int space=data[left].left[pass-1];
		int *temp=new int[pass];
		for(int i=1;i<pass;i++) temp[i]=1;
		while(space)
		{
			for(int i=pass-1;i>=1&&space;i--) temp[i]++,space--;
		}
		cout<<data[left-pass+1].str;
		for(int i=left-pass+2;i<=left;i++)
		{
			for(int j=1;j<=temp[i-(left-pass+2)+1];j++) cout<<" ";
			cout<<data[i].str;
		}
		cout<<endl;
		delete[] temp;
	}
	else cout<<data[left].str<<endl;
}
int calline(int a,int b)
{
    int res=0;
    while(pre[a][b][1])
    {
      int ta=a,tb=b;
      a=pre[ta][tb][0];
      b=pre[ta][tb][1];
      res++;
    }
    return res;
}
int main()
{
//	freopen("formatting.in","r",stdin);
//	freopen("formatting.out","w",stdout);
    char line[101];
	while(true)
	{
		data.clear();
		memset(refer,0,sizeof(refer));
		memset(pre,0,sizeof(pre));
		cin.getline(line,100);
		len=atoi(line);
		if(!len) break;
		while(true)
		{
			cin.getline(line,100);
			if(strlen(line)==0) break;
			int count=1;
			char *p=strtok(line," ");
			data.push_back(point(p));
			while(p=strtok(NULL," "))
			{
				count++;
				data.push_back(point(p));
			}
		}
		init();
		int res=100000000,minline=100000000,in;
		for(int i=1;i<=data[data.size()-1].maxnum;i++)
		{
			int temp;
            if(res>deal(data.size()-1,i))
			   res=deal(data.size()-1,i),minline=calline(data.size()-1,i),in=i;
            else if(res==deal(data.size()-1,i))
            {
                 temp=calline(data.size()-1,i);
                 if(temp<minline)
                     minline=calline(data.size()-1,i),in=i;
            }
		}
		print(data.size()-1,in);
		cout<<endl;
	}
	return 0;
}