hrbust 1476 教主们毕业设计排版【dp】

教主们毕业设计排版

Time Limit: 1000 MS Memory Limit: 65536 K Total Submit: 178(18 users) Total Accepted: 38(17 users) Rating:  Special Judge: No

Description

大四的教主们毕业了。 虽然是教主，但是毕业前都得拿出毕业设计才能得到学士学位，正式毕业。 毕业设计文档的排版有严格要求，排版上不能有一点错误，哪怕已经打印了，也要再修改文档重新打印，所以文档必须排版良好，整齐美观。 然后就有了如下求“整齐度”的简化的题目： 假设正文是n个长度分别为L1、L2、……、Ln（以字符个数度量，不计空白子字符）的单词构成的序列。我们希望将这个段落在一些行上整齐地打印出来，每行至多M个字符。“整齐度”的标准如下：如果某一行包含从i到j的单词（i<j），且单词之间只留一个空格，则在行末多余的空格字符个数为 M - (j-i) - (Li+ …… + Lj)，它必须是非负值才能让该行容纳这些单词。我们希望所有行（除最后一行）的行末多余空格字符个数的立方和最小，这个立方和就是“整齐度”。

Input

有多组测试数据，每组测试数据有两行。 第一行为两个整数n, m，n(1<=n<=2000)表示单词个数， m(1<=m<=500)表示每行最多的字符数。 第二行为正文的n个单词的长度Li(1<=Li<=m)，它们按在正文出出现的顺序给出。

Output

每组测试输出一行，包含一个整数，表示最优整齐度。

Sample Input

5 5 4 1 1 3 3  5 6 1 3 3 2 3

Sample Output

17 1

Source

CLRS ex15-2

Author

《算法导论》

思路：

1、考虑dp，设定dp【i】表示以第i个单词作为一行的结尾的最小花费值 、

那么不难推出其状态转移方程：

dp【i】=min（dp【i】，dp【j-1】+对应从j到i的这一段作为这一行的花费，包括j）；【0<=j<i&&从j到i这一段可以作为一行】；

2、那么接下来考虑最后一段不需要花费，那么其解维护一波最小值即可。

3、注意初始化的值要足够大，数据范围比较大，注意使用long long。

Ac代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define ll long long int
#define inf 2000000000000000000
int n,m;
int a[20050];
int sum[20050];
ll dp[20050];
int main()
{while(~scanf("%d%d",&n,&m)){memset(a,0,sizeof(a));memset(dp,0,sizeof(dp));memset(sum,0,sizeof(sum));for(int i=0;i<n;i++){scanf("%d",&a[i]);if(i==0)sum[i]=a[i];else sum[i]=a[i]+sum[i-1];}for(int i=0;i<n;i++){long long int val=(m-a[i]);val*=(m-a[i]);val*=(m-a[i]);if(i==0){dp[i]=val;}else dp[i]=dp[i-1]+val;for(int j=i-1;j>=0;j--){int len;if(j==0)len=sum[i];else len=sum[i]-sum[j-1];if(len+i-j>m)break;else{long long int dpp;long long int tmp=m-(i-j)-len;tmp*=m-(i-j)-len;tmp*=m-(i-j)-len;if(j-1>=0)dpp=dp[j-1];else dpp=0;dp[i]=min(dp[i],dpp+tmp);}}}ll output=inf;for(int i=n-1;i>=0;i--){int tmp;if(i==0)tmp=sum[n];else tmp=sum[n-1]-sum[i-1];if(tmp+n-1-i>m){output=min(output,dp[i]);break;}else output=min(dp[i],output);}printf("%lld\n",output);}
}