HRBUST 1476 教主们毕业设计排版==算法导论上的思考题整齐打印
| Description |
| 大四的教主们毕业了。 虽然是教主，但是毕业前都得拿出毕业设计才能得到学士学位，正式毕业。 毕业设计文档的排版有严格要求，排版上不能有一点错误，哪怕已经打印了，也要再修改文档重新打印，所以文档必须排版良好，整齐美观。 然后就有了如下求“整齐度”的简化的题目： 假设正文是n个长度分别为L1、L2、……、Ln（以字符个数度量，不计空白子字符）的单词构成的序列。我们希望将这个段落在一些行上整齐地打印出来，每行至多M个字符。“整齐度”的标准如下：如果某一行包含从i到j的单词（i |
| 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 |
思路：dis[i][j]为i, j, 但此间的空格数，dp[i][j]=(给的计算公式)
de[i][j]表示从i到j为一行的空格立方和，
INF (if(dis[i][j]<0)
de[i][j]= 0(if(j==n)
dis[i][j] * dis[i][j] * dis[i][j](dis[i][j]>=0)
dp[i]表示从1到i个单词排版的最小和，dp[i][j]=min{dp[k-1]+de[k][j]}(1<=k<=j)
即dp[n]就是答案
代码如下：
#include#include #include #include usingnamespace std;int dis[2002][2002];longlong dp[2002];longlong de[2002][2002];int main(){int i, j, k, m, n, l;int sum[2005];while(scanf("%d%d",&n,&m)!=EOF){memset(dis,0,sizeof(dis));memset(dp,0,sizeof(dp));memset(sum,0,sizeof(sum));memset(de,0,sizeof(de));int s=0;for(i=1; i<=n; i++)scanf("%d",&l), s+=l, sum[i]=s;sum[0]=0;for(i=1; i<=n; i++)for(j=i; j<=n; j++)dis[i][j]=m-(j-i)-(sum[j]-sum[i-1]);for(i=1; i<=n; i++)for(j=i; j<=n; j++){if(dis[i][j]<0)de[i][j]=LLONG_MAX;elseif(j==n)de[i][j]=0;elseif(dis[i][j]>=0) de[i][j]=dis[i][j]*dis[i][j]*dis[i][j];}dp[0]=0;for(j=1; j<=n; j++){longlong minnum=LLONG_MAX;for(k=1; k<=j; k++){if(de[k][j]==LLONG_MAX||dp[k-1]==LLONG_MAX)continue; minnum=min(minnum, dp[k-1]+de[k][j]);} dp[j]=minnum;}printf("%lld\n", dp[n]);}}
转载于:https://www.cnblogs.com/Hilda/archive/2012/07/31/2616822.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！