首页 > 代码库 > print neatly 整齐打印 算法导论
print neatly 整齐打印 算法导论
作者：jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4098562.html
题目链接：print neatly 整齐打印 算法导论
考虑在一个打印机上整齐地打印一段文章的问题。输入的正文是$n$个长度分别为$L_1,L_2,\dots ,L_n$（以字符个数度量）的单词构成的序列。我们希望将这个段落在一些行上整齐地打印出来，每行至多$M$个字符。“整齐度”的标准如下：如果某一行包含从i到j的单词$(i<j)$，且单词之间只留一个空格，则在行末多余的空格字符个数为 $M - (j-i) - (L_i+ \cdots + L_j)$，它必须是非负值才能让该行容纳这些单词。我们希望所有行（除最后一行）的行末多余空格字符个数的立方和最小。请给出一个动态规划的算法，来在打印机整齐地打印一段又$n$个单词的文章。分析所给算法的执行时间和空间需求。
使用动态规划算法，$dp[i]$表示从第一个单词到第$i$个单词所需要的最小代价。对于每一个单词分别考虑自己单独一行，和前一个单独占据一行$\ldots$ 和前$k$个单词占据一行的情况，其中从$k$到$i$的字符串长度不超过每行最多所能容纳的字符串长度$m$，最后从后向前遍历$dp$数组，计算分别把最后的$k$个单词作为最后一行，且不计算代价的情况下最小的代价。
代码如下：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <cstring> 5 #include <algorithm> 6 #include <limits.h> 7 #define MAXN 2010 8 using namespace std; 9 typedef long long LL;10 LL dp[MAXN], w[MAXN][MAXN]; 11 int len[MAXN]; 12 int n, m;13 LL solve()14 {15 memset(dp, 0, sizeof(dp));16 memset(w, -1, sizeof(w));17 for( int i = 0 ; i <= n ; i++ )18 {19 for( int j = 0 ; j <= n ; j++ )20 {21 w[0][j] = 0;22 }23 }24 for( int i = 1 ; i <= n ; i++ )25 {26 for( int j = i ; j <= n ; j++ )27 {28 int tmp = m - (j-i) - (len[j]-len[i-1]);29 if( tmp < 0 )30 {31 break;32 }33 w[i][j] = tmp*tmp*tmp;34 }35 }36 dp[0] = 0;37 for( int i = 1 ; i <= n ; i++ )38 {39 dp[i] = dp[i-1]+w[i][i];40 for( int j = i-1 ; j >= 0 ; j-- )41 {42 if( w[j+1][i] < 0 ) break;43 dp[i] = min(dp[i], dp[j] + w[j+1][i]);44 }45 }46 LL res = dp[n];47 for( int i = n ; i >= 0 && w[i][n] >= 0 ; i-- )48 {49 res = min(res, dp[i-1]);50 }51 return res;52 }53 int main(int argc, char *argv[])54 {55 while( scanf("%d%d", &n, &m)!=EOF )56 {57 len[0] = 0;58 for( int i = 1 ; i <= n ; i++ )59 {60 scanf("%d", &len[i]);61 }62 for( int i = 2 ; i <= n ; i++ )63 {64 len[i] = len[i-1] + len[i];65 }66 printf("%lld\n", solve());67 }68 }69 //input:(n, m, arr[i])70 //5 571 //4 1 1 3 372 //5 673 //1 3 3 2 374 //output:75 //1776 //1
print neatly 整齐打印 算法导论
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。