poj 1093 Formatting Text

题目链接：http://poj.org/problem?id=1093

题目大意：将一段文字重新排版，每行有n个字符，问最优方案，从后往前dp,令dp[i]为以第i个单词开始到结束的最小badness,并用p[i]记录以i开始的这一行的结束的单词，然后从前往后输出，则能保证空格排列的字典序最小。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int dp[10010],p[10010];
char str[11000];
char w[11000][82];
int n,len[11000],num,cnt,Len;
int count(int sumlen,int j)
{
   // printf("ddd");
    if(j==1)
    return 500;
    int a;
    int q=(n-sumlen)/(j-1);
    int r=(n-sumlen)%(j-1);
    return a=r*q*q+(j-r-1)*(q-1)*(q-1);
   // printf("%d",a)
}
int main()
{
    int i,j,k,rec;
    while(scanf("%d",&n),n)
    {
        getchar();
        len[0]=0;
        num=1;
        cnt=0;
        while(gets(str))
        {
            if(str[0]==0)
                break;
            Len=strlen(str);
            for(i=0;i<Len;i++)
            {
                if(str[i]!=' ')
                {
                    w[num][cnt++]=str[i];
                }
                else if(i&&str[i-1]!=' ')
                {
                    len[num]=len[num-1]+cnt;
                  //  printf("num %d len %d\n",num,len[num]);
                    w[num][cnt]=0;
                    num++;
                    cnt=0;
                }
            }
            len[num]=len[num-1]+cnt; //printf("num %d len %d\n",num,len[num]);
            w[num][cnt]=0;
            num++;
            cnt=0;


        }
        memset(dp,0,sizeof(dp));
        for(i=num-1;i>=1;i--)
        {
         //   printf("i %d %s\n",i,w[i]);
            int MINX=inf;
            for(j=1;i+j-1<num&&len[j+i-1]-len[i-1]+j-1<=n;j++)
            {//printf("aa");
                 rec=dp[i+j]+count(len[i+j-1]-len[i-1],j);
                if(rec<=MINX)//必须小于等于，这样才能保证最小字典序。
                {
                    MINX=rec;
                  //  printf("MIn%d\n",MINX);
                    p[i]=i+j-1;
                }
            }
             dp[i]=MINX;
           //  printf("dp %d\n",dp[i]);
        }
       // printf("p %d\n",p[1]);
        for(i=1;i<=num-1;i=p[i]+1)
        {
            if(p[i]-i+1==1)
            {
                printf("%s\n",w[i]);
                continue;
            }
            int q=(n-(len[p[i]]-len[i-1]))/(p[i]-i);
            int r=(n-(len[p[i]]-len[i-1]))%(p[i]-i);
          //  printf("q %d r %d\n",q,r);
            for(j=i;j<p[i];j++)
            {
                printf("%s",w[j]);
                for(k=1;k<=(j-i+1>p[i]-i-r)+q;k++)
                    printf(" ");

            }
            printf("%s\n",w[p[i]]);
        }
        puts("");

    }
}