首页 > 代码库 > uva709 - Formatting Text(递推)

uva709 - Formatting Text(递推)

题目:uva709 - Formatting Text(递推)


题目大意:给你一段文章,里面有很多的单词。要求你排版,按照题目给定的长度,并且要求每一行要以单词开头,单词结束。如果一行只有一个单词的话,就放在最开头。并且根据badness最小来排版。


解题思路:这题知道是DP就不难想到状态,但是这题要考虑很多的细节问题,例如:一行只要一个单词的话,就要直接回车,不能再输出空格,因为这个PE了。而且还有单独一行一个单词,如果这个单词的长度小于要求的长度,那么badness = 500;并且这里要求的是前面的单词之间的间隙比较小,那么就需要从后面往前面递推,还需要考虑这个单词是否放单独的一行最优,还是后面接个单词比较优,总之好麻烦,一不当心就会错。

状态转移:dp【i】【j】 (第i个单词放在它所在的那一行的j位置(起始处)) dp【i】【j - l【i】 + k】 = dp【i + 1】【j】 + (k - 1) * (k - 1); k是空格数,注意j - l【i】 + k要在0 -- L - l【i】之间,并且这里的k当j == 0的时候可以等于0,相当于这两个单词在两行。其余的时候就至少要等于1.然后还要单独的考虑自己一行的情况。


代码:

#include <cstdio>
#include <cstring>

const int N = 10005;
const int M = 85;
const int INF = 0x3f3f3f3f;

int L, n;
int dp[N][M];
int p[N][M];//路径
char str[N];
char word[N][M];
int l[N];//单词长度

int Min (const int a, const int b) { return a < b ? a: b; }

void handle () {处理输入

	int j = 0;
	bool flag = 0;
	for (int i = 0; i <= strlen (str); i++) {

		if (str[i] != ' ' && str[i] != '\0') {
			word[n][j++] = str[i];		
			flag = 1;
		} else {
			if (flag) {
				word[n][j] = '\0'; 
				l[n++] = j;
				j = 0;
				flag = 0;
			}
		}
	}
}

void printf_ans (int x, int y) {//输出路径

	if (x == n + 1)
		return;
	if (!p[x][y] && !y) {//单独一行不要输出空格直接回车
		printf ("%s", word[x - 1]);
	} else {

		printf ("%s", word[x - 1]);
		if (x != n) {
			for (int i = y + l[x - 1]; i < p[x][y]; i++)
				printf (" ");
		}
	}

	if (!p[x][y] || x == n)
		printf ("\n");
	printf_ans(x + 1, p[x][y]);		
}

int main () {

	int tmp;
	while (scanf ("%d%*c", &L), L) {

		n = 0;
		while (gets(str) && str[0] != '\0') {

			handle();				
		}
		//init
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= L; j++) {
				dp[i][j] = INF;
				p[i][j] = L + 1;
			}
		dp[n][0] = 500;
		p[n][0] = 0; 
		dp[n][L - l[n - 1]] = 0;

		for (int i = n - 1; i >= 1; i--) { 
			for (int j = 0; j <= L - l[i]; j++) {

				if (dp[i + 1][j] == INF)
					continue;
				if (!j) {

					if (dp[i + 1][j] <= dp[i][L - l[i - 1]]) {//两个单词在两行的情况
						dp[i][L - l[i - 1]] = dp[i + 1][j];
						p[i][L - l[i - 1]] = j;
					}
					tmp = (l[i - 1] == L) ? 0: 500;
					if (dp[i + 1][j] + tmp <= dp[i][0]) {//单独一行
						dp[i][0] = dp[i + 1][j] + tmp;
						p[i][0] = j;
					}

				} else {

					for (int k = 0; k < j - l[i - 1]; k++) {//中间有空格的情况

						tmp = j - l[i - 1] - k - 1;
						if (dp[i + 1][j] + tmp * tmp < dp[i][k]) {

							dp[i][k] = dp[i + 1][j] + tmp * tmp;
							p[i][k] = j;
						} else if (dp[i + 1][j] + tmp * tmp == dp[i][k]) {

							if (p[i][k] > k)//如果后面可以接单词的话,那么就不要单独一行
								p[i][k] = Min (p[i][k], j);//使得前面的空格尽量少
							else 
								p[i][k] = j;			
						}
					}
				}
			}
		}

		printf_ans(1, 0);
		printf ("\n");
	}
	return 0;  
}



uva709 - Formatting Text(递推)