制作平台网站方案,wordpress没有找到站点,建盏的好坏怎么区分,电脑网络服务器在哪里文章目录 问题描述算法原理算法实现参考资料 问题描述 给定由n个英文单词组成的一段文章#xff0c;每个单词的长度 (字符个数)依序为 l 1 , l 2 , . . . , l n l_1, l_2, ..., l_n l1,l2,...,ln。要在一台打印机上将这段文章“漂亮”地打印出来。打印机每行最多可打印 … 文章目录 问题描述算法原理算法实现参考资料 问题描述 给定由n个英文单词组成的一段文章每个单词的长度 (字符个数)依序为 l 1 , l 2 , . . . , l n l_1, l_2, ..., l_n l1,l2,...,ln。要在一台打印机上将这段文章“漂亮”地打印出来。打印机每行最多可打印 M个字符。这里所说的“漂亮”的定义如下在打印机所打印的每一行中行首和行尾可不留空格行中每两个单词之间留一个空格如果在一行中打印从单词i到单词j的字符则按打印规则应在一行中恰好打印 Σ k i j l k j − i \Sigma_{ki}^{j}l_kj-i Σkijlkj−i个字符包括字间空格字符且不允许将单词打破多余的空格数为 M − Σ k i j l k − j i M-\Sigma_{ki}^{j}l_k-ji M−Σkijlk−ji除文章的最后一行外希望每行多余的空格数尽可能少。因此以各行(最后一行除外)的多余空格数的立方和达到最小作为“漂亮”的标准。试用动态规划算法设计一个“漂亮打印”方案并分析算法的计算复杂性。
算法原理
本题使用动态规划算法求解需要维护三个数组分别是
extra[i][j]表示如果第i到第j个单词放到同一行那么这行有多少个剩余空格lc[i][j]从第i到第j个单词放到同一行那么这行空格数的立方值。维护这个数组会出现以下三种情况 extra[i][j] 0本行由于字符数M限制不能容纳i到j个单词lc[i][j] INFj n extra[i][j] 0文章最后一行不计入统计范围lc[i][j] 0除以上两种情况之外lc[i][j] extra[i][j]的立方; c[i]文章从第1到j个单词的空格立方之和
动态规划状态转移方程如下 l c [ i ] [ j ] { inf , e x t r a [ i ] [ j ] 0 0 , j n e x t r a [ i ] [ j ] 0 ( e x t r a s [ i ] [ j ] ) 3 , e l s e lc[i][j]\left\{ \begin{aligned} \inf , {extra[i][j]0}\\ 0, { j n \\ extra[i][j] 0 }\\ (extras[i][j])^3, {else}\\ \end{aligned} \right. lc[i][j]⎩ ⎨ ⎧inf,0,(extras[i][j])3,extra[i][j]0jnextra[i][j]0else c [ j ] { 0 , j 0 m i n ( c [ i − 1 ] l c [ i ] [ j ] , c [ j ] ) , j 0 c[j]\left\{ \begin{aligned} 0, {j0}\\ min(c[i - 1] lc[i][j], c[j]), {j0}\\ \end{aligned} \right. c[j]{0,min(c[i−1]lc[i][j],c[j]),j0j0
综上我们得到这三个数组那又该如何得出每行的划分位置呢 在每次更新c[j]时记录position[j] i即对于以单词j为结尾的一行来说本行最佳起始位置为单词i。由于动态规划更新的每一个数值都是当前及之前的最优解因此全局最优解就是最后一个数值。position数组中很多值都是无意义的因为动态规划是从前往后算的但是只有最后的数值才是全局的最优输出时由果导因即从后往前看。
算法实现
#include bits/stdc.h
#define INF 1000
using namespace std;int wordsLen(int wordsL[], int i, int j) {//计算从i到j的单词总长度int sum 0;for (int k i; k j; k) {sum wordsL[k];}return sum;
}int main() {int n, M, extra[100][100], lc[100][100], c[100], l[100], position[100];string words[100];c[0] 0;cin n M;//n个单词每行最多M个字符for (int i 1; i n; i) {cin words[i];l[i] words[i].size();c[i] INF;}for (int i 1; i n; i) { //此行从第i个开始放for (int j i; j n; j) { //放到第j个extra[i][j] M - j i - wordsLen(l, i, j); //如果i到j放到一行那么这行有多少个剩余空格if (extra[i][j] 0) //这行放不下这么多单词lc[i][j] INF;else if (j n extra[i][j] 0) //最有一行lc[i][j] 0;else //正常情况lc[i][j] pow(extra[i][j], 3);if (c[i - 1] lc[i][j] c[j]) { //从i处分行是否空格更少c[j] c[i - 1] lc[i][j]; //整篇文章从1到j存放单词的空格立方之和//position数组很多值都是无意义的因为动态规划是从前往后算的但是只有最后的数值才是全局的最优输出时由果导因即从后往前看。position[j] i; //对于以j为结尾的一行来说本行最佳起始位置为i}}}stackint st;int i n;while(i0) {st.push(position[i]);i position[i]-1;}st.pop();for (int i 1; i n; i) {if (!st.empty()i st.top()){cout endl;st.pop();}cout words[i] ;}cout \n总剩余空格数 c[n];return 0;
}
/*
10 8
abc de h polq cs opaqe gh t asd th
*/参考资料
动态规划之整齐打印动态规划——漂亮打印问题
