1300 文件排版
時間限制: 1 s

空間限制: 128000 KB

題目描述 Description

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

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

---

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+7*7=50，而第二個例子的難看程度僅為1+1+1+4+1+4=12。

輸出時，每一行的開頭和結尾處都必須是一個單詞，即每行開頭和結尾處不能有空白。唯一例外的是該行僅有一個單詞組成的情況，對于這種情況你可將單詞放在該行開頭處輸出，此時如果該單詞比該行應有的長度短則我們指定它的最壞程度為500，當然在這種情況下，該行的實際長度即為該單詞的長度。

輸入描述 Input Description

輸入文件第一行是一個整數N，表示該段要求達到的寬度，1<=N<=80。該段文章由一個或多個單詞組成，單詞由ASCII碼值為33到126（包含33和126）的字符組成，單詞與單詞之間用空格隔開（可能超過一個）。單詞長度不會超過段落要求達到的寬度。一段文字所有單詞的總長度不會超過10000個字符，任何一行都不會超過100個字符，任何一個單詞都在同一行內。

輸出描述 Output Description

對于每個段落，找出使其難看程度最小的排版形式并輸出句子：“Minimal badness is B.”,B是指按可能的最好排版形式會發生的難看程度值。注意排版后文本行數任意，多余的空格也可刪除。

樣例輸入 Sample Input

28

This is the example you are

actually considering.

樣例輸出 Sample Output

Minimal badness is 12.

分析：
只有通過把空格平均化 越是平均的空格 丑陋值越小
任何一個詞作為結尾的最少丑陋值是$f[i]$
轉移方程為 $f[i]=min(f[i],f[j?1]+cost(j,i));$
$cost(j,i)$為平均化j~i號詞的花費

#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #include<climits>using namespace std; typedef long long ll; const int maxn = 0x3f3f3f3f; char a[110]; int sum[10010],n; ll dp[10010]; int cost(int i,int j){if(!(i^j)){if(!((sum[i]-sum[j-1])^n))return 0;return 500;}int blank = n-(sum[i]-sum[j-1]);int num = i-j;//分割數量if(blank<num)return maxn;int avg = blank/num;int y = blank-avg*num;avg--;return num*1LL*(avg)*(avg)+1LL*y*(avg<<1|1); } int main() {int cnt=1;scanf("%d",&n);while(~scanf("%s",a)){sum[cnt] = sum[cnt-1]+strlen(a);cnt++;}for(int i=1;i<=cnt;i++)dp[i] = maxn;for(int i=1;i<=cnt-1;i++){for(int j=1;j<=i;j++){dp[i] = min(dp[i],dp[j-1]+cost(i,j));}}printf("Minimal badness is %lld.\n",dp[cnt-1]);return 0; }

總結

以上是生活随笔為你收集整理的CodeVS 1300 文字排版 线性DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。