codevs 1300：文件排版（DP）

题目描述

写电子邮件是有趣的，但不幸的是经常写不好看，主要是因为所有的行不一样长，你的上司想要发排版精美的电子邮件，你的任务是为他编写一个电子邮件排版程序。

完成这个任务最简单的办法是在太短的行中的单词之间插入空格，但这并不是最好的方法，考虑如下例子：

This is the example you are

actually considering.

假设我们想将第二行变得和第一行一样长，靠简单地插入空格则我们将得到如下结果：

This is the example you are

actually considering.

但这太难看了，因为在第二行中有一个非常大的空白，如果将第一行的单词“are”移到下一行我们将得到较好的结果：

This is the example you

are actually considering.

当然，这必须对难看程度进行量化。因此我们必须给出单词之间的空格的难看程度，一个包含NNN个空格符的空白段，其难看程度值为(n−1)2(n-1)^2(n−1)2，程序的目的是使难看程度的总和最小化。例如，第一个例子的难看程度是1+7×7=501+7\times7=501+7×7=50，而第二个例子的难看程度仅为1+1+1+4+1+4=121+1+1+4+1+4=121+1+1+4+1+4=12。

输出时，每一行的开头和结尾处都必须是一个单词，即每行开头和结尾处不能有空白。唯一例外的是该行仅有一个单词组成的情况，对于这种情况你可将单词放在该行开头处输出，此时如果该单词比该行应有的长度短则我们指定它的最坏程度为500500500，当然在这种情况下，该行的实际长度即为该单词的长度。

输入描述

输入文件第一行是一个整数N，表示该段要求达到的宽度，1≤N≤801\leq N\leq 801≤N≤80。该段文章由一个或多个单词组成，单词由ASCII码值为333333到126126126（包含333333和126126126）的字符组成，单词与单词之间用空格隔开（可能超过一个）。单词长度不会超过段落要求达到的宽度。一段文字所有单词的总长度不会超过100001000010000个字符，任何一行都不会超过100100100个字符，任何一个单词都在同一行内。

输出描述

对于每个段落，找出使其难看程度最小的排版形式并输出句子：“Minimal badness is B.”,B是指按可能的最好排版形式会发生的难看程度值。注意排版后文本行数任意，多余的空格也可删除。

样例输入

28

This is the example you  are

actually considering.

样例输出

Minimal badness is 12.

Solve

二维的DP：

状态dp[i][j]dp[i][j]dp[i][j]表示第iii个单词末尾放在jjj位置的最小难看程度

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define ms(a,b) memset(a,b,sizeof(a))

#define INF 0x7f7f7f7f

const int maxn=1e3+10;

const int mod=1e9+7;

using namespace std;

char ch[maxn];

// dp[i][j]表示第i个单词末尾放到位置j的最小难看程度

int dp[maxn][maxn];

int len[maxn];

int main(int argc, char const *argv[])

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;

    cin>>n;

    int cnt=0;

    while(cin>>ch)

        len[++cnt]=strlen(ch);

    ms(dp,INF);

    dp[1][n]=500;

    dp[1][len[1]]=0;

    for(int i=2;i<=cnt;i++)

        for(int j=len[i];j<=n;j++)

        {

            int res=j-len[i];

            // 如果是某行的第一个单词，继承上一行的最后一个状态

            if(!res)

                dp[i][j]=dp[i-1][n];

            else

            {

                if(j==n)

                    dp[i][j]=dp[i-1][j]+500;

                for(int k=0;k<res;k++)

                    dp[i][j]=min(dp[i][j],dp[i-1][k]+(res-k-1)*(res-k-1));

            }

        }

    cout<<"Minimal badness is "<<dp[cnt][n]<<"."<<endl;

    return 0;

}

一维的DP

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define ms(a,b) memset(a,b,sizeof(a))

#define INF 0x7f7f7f7f

const int maxn=1e6+10;

const int mod=1e9+7;

using namespace std;

char ch[maxn];

// dp[i]表示以第i个单词作为一行的结尾的最小难看程度

// dp[i]=min(dp[i]+cost(j,i))

// cost(j,i)表示j+1到i在同一行的最小难看程度

// 当空格在一行内平分的时候难看程度最小

int dp[maxn];

int len[maxn];

inline int calc(int l,int r,int n)

{

    if(l==r)

    {

        if(len[r]-len[l-1]==n)

            return 0;

        return 500;

    }

    // 一行内的空格数

    int res=n-(len[r]-len[l-1]);

    // 一行内至少要有r-l个空格】

    if(res<r-l)

        return INF;

    // 将空格平分

    int space=res/(r-l);

    // 多余的空格往之前的空格段中平分,每段至多一个

    int more=res%(r-l);

    space-=1;

    return space*space*(r-l)+more*(space*2+1);

}

int main(int argc, char const *argv[])

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;

    int cnt=0;

    cin>>n;

    while(cin>>ch)

        len[++cnt]=len[cnt-1]+strlen(ch);

    ms(dp,INF);

    dp[0]=0;

    for(int i=1;i<=cnt;i++)

        for(int j=1;j<=i;j++)

            dp[i]=min(dp[i],dp[j-1]+calc(j,i,n));

    cout<<"Minimal badness is "<<dp[cnt]<<"."<<endl;

    return 0;

}

巴特西