【5002】排版問題

Time Limit: 3 second

Memory Limit: 2 MB

【問題描述】

寫電子郵件是有趣的，但不幸的是經常寫不好看，主要是因為所有的行不一樣長，你的上司想要發排版精美的
           

電子郵件，你的任務是為他編寫一個電子郵件排版程式。

完成這個任務最簡單的辦法是在太短的行中的單詞之間插入空格，但這并不是最好的方法，考慮如下例子:

******************(這裡的28個*表示要達到的行寬)

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.

當然，這必須對難看程度進行量化。是以我們必須給出單詞之間的空格的難看程度，一個包含n個空格符的空白

處，其難看程度值為(n-1)2，程式的目的是使難看程度的總和最小化。例如，第一個例子的難看程度是1+72=50,而

第二個例子的難看程度僅為1+1+1+4+1+4=12。

輸出時，每一行的開頭和結尾處都必須是一個單詞,即每行開頭和結尾處不能有空白。唯一例外的是該行僅有一

個單詞組成的情況，對于這種情況你可将單詞放在該行開頭處輸出,此時如果該單詞比該行應有的長度短則我們指定

它的最壞程度為500，當然在這種情況下，該行的實際長度即為該單詞的長度。

【輸入】

第一行是一個整數N，表示該段要求達到的行寬度，1<=N<=80。
第二行起為文章内容，該段文章由一個或多個單詞組成,單詞由ASCII碼值為33到126(包含33和126)的字元組成,
           

單詞與單詞之間用空格隔開(空格的ASCII碼是32,可能超過一個)。單詞長度不會超過段落要求達到的寬度。一段文字

所有單詞的總長度不會超過10000個字元，任何一行都不會超過100個字元，任何一個單詞都在同一行内。

文章若從鍵盤輸入，按”F6”鍵或”Ctrl+Z”鍵結束，導緻eof()為真。

【輸出】

對于輸入的文章段落,找出使其難看程度最小的排版形式并輸出句子:“Minimal badness is B.”,B是指按可能
           

的最好排版形式會發生的難看程度值。注意排版後文本行數任意，多餘的空格或其他控制符号也可删除。

【輸入樣例】

28

This is the example you are

actually considering.

【輸出樣例】

Minimal badness is 12.

【題目連結】:http://noi.qz5z.com/viewtask.asp?id=5002

【題解】

可以把中間的那些空格去掉；直接擷取所有的單詞;存在一個vector裡面

設f[i]表示以第i個單詞當做一行的最後一個單詞的最少難看程度;

分兩種轉移方式：

1.把第i個單詞放在新的一行。題目有說如果這個單詞小于需要的長度,則難看程度為500;

2.把第k到第i個單詞放在新的一行；

那麼問題在于怎麼讓k到i這些單詞放在一行形成的難看程度最小?

必然是讓每兩個單詞之間的空格平均分;即用n減去從k到i這些單詞的總長度;設差為rest;則這rest個位置就是要用來加空格的。那麼就盡量平方這些空格;

搞個g[i][j]表示從第i到第j個單詞放在同一行且這一行隻有這些單詞時最小難看程度;用遞歸搞出g(i,j)就好;用遞歸搞，并不是真的一個數組;

再具體一點

f[] = ;
for (i= -> n)
{
    if (len[i]!=n)
        f[i] = f[i-]+;
    else
        f[i] = f[i-];//難看程度為0
    for (k= -> i-)
        {
            int temp = f[k-]+g(k,i);
            if (temp < f[i])
                f[i] = temp;
        }
}
           

【完整代碼】

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MAXN = +;

char s[];

int n,f[MAXN],sum[MAXN];
vector <int> a;

int sqr(int x)
{
    return x*x;
}

int g(int l,int r)
{
    int tlen = sum[r] - sum[l-],kg = r-l;
    if (tlen+kg>n)
        return ;
    tlen = n-tlen;
    if (!(tlen%kg))
        return kg*sqr((tlen/kg)-);
    else
    {
        int i = tlen/kg,rest = tlen % kg;
        return kg*sqr(i)-(kg-rest)*(*i-);//把每兩個單詞之間的空格個數當做i+1來做
        //然後再減去多餘的
        //i^2-(i-1)^2 = 2*i-1;
    }
}

int main()
{
    //freopen("F:\\rush.txt","r",stdin);
    scanf("%d",&n);
    a.push_back(-);
    while (~scanf("%s",s))
    {
        int i = a.size(),len = strlen(s);
        sum[i] = sum[i-]+len;
        a.push_back(len);
    }
    int len = a.size()-;
    f[] = ;
    for (int i = ;i <= len;i++)
    {
        if (a[i] == n)
            f[i] = f[i-];
        else
            f[i] = f[i-] + ;
        for (int k = ;k <= i-;k++)
        {
            int temp = f[k-]+g(k,i);
            if (temp < f[i])
                f[i] = temp;
        }
    }
    printf("Minimal badness is %d.\n",f[len]);
    return ;
}
           

轉載于:https://www.cnblogs.com/AWCXV/p/7632052.html