Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

来来来,贴代码了

Posted by 278466061 at 2015-02-02 11:12:39 on Problem 1093
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <memory.h>
#include<algorithm>
using namespace std;

#define MAX 10000
string paragraph[MAX+10];
int lengths[MAX+10];
int dps[MAX+10];
int ans[MAX+10];
int N, total;

void _Space_Divide(int spaces, int words, int* divides)
{
	int i;
	int gaps = words - 1;
	for(i = 0; i < gaps; ++i)
		divides[i] = spaces/gaps;
	spaces -= divides[0]*gaps;
	i = gaps-1;
	while(spaces)
	{
		++divides[i];
		--spaces;
		--i;
	}
}

int _Badness_Count(int spaces, int words)
{
	if(words==1)
	{
		if(spaces)
			return 500;
		else
			return 0;
	}
	int badness = 0;
	int* divides = new int[words-1];
	_Space_Divide(spaces, words, divides);
	for(int i = 0; i < words-1; ++i)
		badness += (divides[i]-1)*(divides[i]-1);
	return badness;
}

int foo(int current)
{
	int min = MAX*10;
	int total_length = 0;
	int length;
	for(int n = 0; current+n < total; ++n)
	{
		total_length += lengths[current+n];
		if(total_length+n > N)
			break;
		int tmp = _Badness_Count(N-total_length, n+1)+dps[current+n+1];
		if(tmp <= min)
		{
			min = tmp;
			length = n+1;
		}
	}
	dps[current] = min;
	ans[current] = length;
	return min;
}

void display()
{
	int i, j;
	int current = 0;
	while(current < total)
	{
		int n = ans[current];
		int spaces = N;
		for(i = current; i < current+n; ++i)
			spaces -= lengths[i];
		int* divides;
		if(n > 1)
		{
			divides = new int[n-1];
			_Space_Divide(spaces, n, divides);
			for(i = 0; i < n-1; ++i)
			{
				cout << paragraph[current+i];
				for(j = 0; j < divides[i]; ++j)
					cout << " ";
			}
			cout << paragraph[current+n-1] << endl;
		}
		else
		{
			cout << paragraph[current];
			for(i = 0; i < spaces; ++i)
				cout << " ";
			cout << endl;
		}
		current += n;
	}
	cout << endl;
}

int main()
{
	//ifstream cin("test.txt");
	int i, j;
	char line[110];
	string word;
	while(cin >> N)
	{
		memset(lengths, 0, sizeof(lengths));
		memset(dps, 0, sizeof(dps));
		if(!N)
			break;
		cin.getline(line, 80);
		j = 0;
		while(cin.getline(line, 110))
		{
			if(!strlen(line))
			{
				total = j;
				for(i = total-1; i >= 0; --i)
					foo(i);
				//cout << dps[0] << endl; 
				display();
				break;
			}
			for(i = 0; i < strlen(line); )
			{
				if(line[i]!=' ')
					word += line[i++];
				else if(line[i]==' ')
				{
					paragraph[j] = word;
					lengths[j] = word.length();
					++j;
					//cout << word << endl;
					word = "";
					while(line[i]==' ')
						++i;
				}
			}
			if(word.length())
			{
				paragraph[j] = word;
				lengths[j] = word.length();
				++j;
				//cout << word << endl;
				word = "";
			}
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator