首页 > 代码库 > 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(递推)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。