作者：jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4098562.html
考虑在一个打印机上整齐地打印一段文章的问题。输入的正文是$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$个单词作为最后一行，且不计算代价的情况下最小的代价。
代码如下：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits.h>
#define MAXN 2010
using namespace std;
typedef long long LL;
LL dp[MAXN], w[MAXN][MAXN];
int len[MAXN];
int n, m;
LL solve()
{
memset(dp, , sizeof(dp));
memset(w, -, sizeof(w));
for( int i = ; i <= n ; i++ )
{
for( int j = ; j <= n ; j++ )
{
w[][j] = ;
}
}
for( int i = ; i <= n ; i++ )
{
for( int j = i ; j <= n ; j++ )
{
int tmp = m - (j-i) - (len[j]-len[i-]);
if( tmp < )
{
break;
}
w[i][j] = tmp*tmp*tmp;
}
}
dp[] = ;
for( int i = ; i <= n ; i++ )
{
dp[i] = dp[i-]+w[i][i];
for( int j = i- ; j >= ; j-- )
{
if( w[j+][i] < ) break;
dp[i] = min(dp[i], dp[j] + w[j+][i]);
}
}
LL res = dp[n];
for( int i = n ; i >= && w[i][n] >= ; i-- )
{
res = min(res, dp[i-]);
}
return res;
}
int main(int argc, char *argv[])
{
while( scanf("%d%d", &n, &m)!=EOF )
{
len[] = ;
for( int i = ; i <= n ; i++ )
{
scanf("%d", &len[i]);
}
for( int i = ; i <= n ; i++ )
{
len[i] = len[i-] + len[i];
}
printf("%lld\n", solve());
}
}
//input:(n, m, arr[i])
//5 5
//4 1 1 3 3
//5 6
//1 3 3 2 3
//output:
//17
//
