location allocation problem（facility location problem）

給定許多個地點，設立p個聯絡站，使得每一個地點皆可被其中一間聯絡站聯絡到，而且越有效率越好。

深入地定義「效率」的意義，得以細分許多問題：

p-median problem：令聯絡站離各地點的距離總和最小。
p-center problem：令聯絡站離各地點的距離最大值最小。
uncapacitated facility location problem：在各地設立聯絡站需要成本，
但建立聯絡站後會從周遭地點獲得利益，令設立聯絡站後利益最大。
range assignment problem：令各地點離聯絡站的中繼點不超過一定數量。

這些問題在現實生活中的應用，例如超商的物流通路、有線電視的纜線鋪設、基地台的設立位置等等。可惜這些問題已經被證明是NP-hard問題，無法快速得到精準解答。

以下只討論一維版本。所有的地點和連絡站都在數線上。

p-median problem

給定許多個地點，設立p個聯絡站，使得每一個地點皆可被其中一間聯絡站聯絡到。令聯絡距離的總和最小。

此處討論一維版本，地點和連絡站落於數線上。

簡化問題、觀察問題：只有一個連絡站

將聯絡站放在中位數是最好的。如果中位數是在兩個位置中間，那麼聯絡站可以游移於兩個位置之間、其上，不會改變聯絡距離的總和。所有的聯絡站都可以挪至地點之上！

證明不難。試著移動聯絡站，讓各個地點的聯絡距離此消彼長，觀察一下就會明白了。動手試試看吧！

另外也得到一個重要的結論：所有的聯絡站都可以挪至地點之上，而不會改變聯絡距離的總和。

簡化問題、觀察問題：只有一個地點

將全部的聯絡站放在該地點上是最好的。

聯絡站全部疊在一起，有摩肩接踵、水洩不通的感覺，理當好好分配才對。說到分配，如果聯絡站數量大於等於地點數量，只要將聯絡站安排在各個地點上，聯絡距離的總和就是零了。

簡化問題、觀察問題：地緣

為了拉近聯絡距離，所有地點都會連向最近的聯絡站，而不會有捨近求遠的情形。換個觀點來看，一個聯絡站只會連向鄰近的地點，而不會有捨近求遠的情形。

p-median problem可以重新想成：依照地緣，所有地點分配成p個區域，每一區自行設立一個聯絡站，位於中位數，可挪至鄰近地點。

至此，p-median problem就成了如何分區的問題。

簡化問題、觀察問題：分區

如果有地點選擇聯絡站時捨近求遠，表示這種分區方式不好。

各個區域之間相鄰越遠越好？大家自行觀察看看吧。

動態規劃

聯絡距離的總和，可以以區為單位，分別計算，最後再統計——這就是在分割問題。

拿掉最邊邊的一區、拿掉該區的聯絡站，如此便縮小了問題範疇，讓小問題與原問題類似。接著窮舉該區的各種大小，求得遞迴式。

注意別讓剩下來的地點太少、剩下的聯絡站太多，而導致連絡站重疊。妥善分配重疊的聯絡站，一定能使聯絡距離的總和更小。沒有必要枚舉出讓聯絡站重疊的分區方式。

f(p, n) = 
 ⎧ min( f(p-1, p-1) + d(p  , n) ,
 ⎪      f(p-1, p  ) + d(p+1, n) ,
 ⎪      ...                     ,
 ⎨      f(p-1, n-2) + d(n-1, n) ,
 ⎪      f(p-1, n-1) + d(n  , n) )  if p < n  && n >= 0
 ⎪
 ⎪ 0                               if p >= n && n >= 0
 ⎩ +inf                            otherwise

p：已設立了p個聯絡站。
n：已涵蓋了第1個到第n個地點。
f(p, n)：設立p個聯絡站，涵蓋第1個到第n個地點時，其聯絡距離的總和。
d(i, j)：第i個地點到第j個地點所構成的區域，其聯絡距離的總和最小值。
         可利用中位數算得。

N為地點個數，P為聯絡站個數。總共O(NP)個子問題，計算一個子問題需時O(N)，時間複雜度O(N²P)。

int P = 3, N = 6; // P為聯絡站個數，N為地點個數。 // 為了方便實作，數字右移一格。 int location[6+1] = {0, 2, 6, 11, 14, 18, 26}; // 需要排序 int d[6+1][6+1]; // 各種區域，其聯絡距離的總和。 int f[3+1][6+1]; // DP表格 int r[3+1][6+1]; // 記錄最佳的分界線位置。 void p_median() { // preprocessing。計算各種區域，其聯絡距離的總和。 for (int i=1; i<=N; ++i) for (int j=i; j<=N; ++j) { int m = (i+j)/2; // 聯絡站位於中位數 d[i][j] = 0; // 聯絡距離的總和 for (int k=i; k<=j; ++k) d[i][j] += abs(location[k] - location[m]); } // dynamic programming。求出聯絡距離的總和最小值。 memset(f, 0, sizeof(f)); // f[0][...] = 0; for (int p=1; p<=P; ++p) for (int n=1; n<=N; ++n) { // 計算子問題f(p, n) f[p][n] = 1e9; for (int k=p; k<=n; ++k) if (f[p-1][k-1] + d[k][n] < f[p][n]) { f[p][n] = f[p-1][k-1] + d[k][n]; r[p][n] = k; // 從第k個位置往右到第j個位置 // 都屬於這個區域 } } cout << "聯絡距離的總和最小值是" << f[P][N]; }

動態規劃：monotonicity

不難發現，分界線位於最適中、最均衡的位置，讓聯絡距離的總和最小。

觀察地點逐步增加的問題們。最佳分界線漸漸右移。

觀察聯絡站逐步增加的問題們。最佳分界線漸漸右移。

因此我們不必窮舉所有的區域大小！但是時間複雜度仍是O(N²P)。

...... memset(f, 0, sizeof(f)); memset(r, 0, sizeof(r)); // 初始化為零 ...... f[p][n] = 1e9; int kk = max(i, r[p][n-1], r[p-1][n]); for (int k=kk; k<=n; ++k) // 加速 if (f[p-1][k-1] + d[k][n] < f[p][n]) ......

UVa 662

動態規劃：convex hull

採用convex hull加速，斜率皆是1，可視作deque加速，時間複雜度O(NP)。

p-center problem

給定許多個地點，設立p個聯絡站，使得每一個地點皆可被其中一間聯絡站聯絡到。令聯絡距離的最大值最小。

也可以想做是：各個聯絡站各自使用一個圓，以自己為圓心，向外擴張以包住其負責的地點，然後讓最大的圓的半徑越小越好。

p-center problem的主要應用是設立基地台。基地台放送電波，地點距離越遠，就需要越多能量、耗費越多電能；跟地點個數無關。為了節省電能，所以要適當的安排基地台的位置，縮短電波的放送距離。

此處依舊討論一維版本。

簡化問題、觀察問題：只有一個連絡站

聯絡站放在相離最遠的兩個地點的正中央是最好的。應該不用證明了吧？

其他性質皆與p-median problem類似，不再複述。

p-center problem可以重新想成：依照地緣，所有地點分配成p個區域，找出最寬的區域，其寬度的一半，即是答案。

簡化問題、觀察問題：分區

p-center problem只關心最寬的區域，其餘區域的寬度根本無所謂，不要超過最寬的區域就好了。

動態規劃：monotonicity

p-center problem特性更強。分界線往右移動，一旦左方最寬的區域的寬度（的一半），大於等於右方區域的寬度（的一半），分界線就沒有必要繼續往右移動。往右移動只會讓答案更大。

p-median problem僅掌握分界線的起點。p-center problem同時掌握起點與終點，時間複雜度O(NP)。

此技巧尚無正式名稱，英文網路稱作「divide-and-conquer optimization」。

int P = 3, N = 6; // P為聯絡站個數，N為地點個數。 // 為了方便實作，數字右移一格。 int location[6+1] = {0, 2, 6, 11, 14, 18, 26}; // 需要排序 int f[3+1][6+1]; // DP表格 int r[3+1][6+1]; // 記錄最佳的分界線位置。 inline int d(int i, int j) { return location[j] - location[i]; } void p_center() { // dynamic programming。求出最寬的區域最窄可為多少。 memset(f, 0x7f, sizeof(f)); // 初始化為無限大 f[0][0] = 0; for (int p=2; p<=P; ++p) for (int n=1, k=1; n<=N; ++n) { // 找出最佳的分界線 while (k <= n && f[p-1][k-1] <= d(k, n)) k++; k--; // 用最佳的分界線，算得子問題的答案。 f[p][n] = f[p-1][k-1] + d(k, n); r[p][n] = k; // 從第k個位置往右到第j個位置 // 都屬於這個區域 } cout << "「最寬的區域」最窄為" << f[P][N]; }

試誤法：窮舉最寬的區域的寬度

p-center problem只關心最寬的區域。這種情況下，可以直接令每個區域都一樣大，跟最寬的區域一樣大，從第一個地點開始分區，儘量涵蓋越多地點。若能涵蓋全部地點，表示此寬度可行。

「最寬的區域」寬度適中，區域數量正確，可能是答案。

「最寬的區域」寬度太大，區域數量太少，可能是答案。

「最寬的區域」寬度太小，區域數量太多，不可能是答案。

寬度總共O(N²)種，驗證一種寬度需時O(N)，時間複雜度O(N³)。

或者實施排序、二元搜尋，時間複雜度O(N²logN)。

或者length(i,j)是已排序矩陣，樓梯搜尋，時間複雜度O(N²)；二維二元搜尋，時間複雜度O(NlogN)。

或者寬度取實際數值。下限是0，上限是最遠的兩個地點的距離L。時間複雜度O(NlogL)。

int P = 3, N = 6; // P為聯絡站個數，N為地點個數。 // 為了方便實作，數字右移一格。 int location[6+1] = {0, 2, 6, 11, 14, 18, 26}; // 需要排序 // 計算分區數目 int interval_number(int max_interval_width) { int count = 1, s = 1; for (int i=1; i<=N; ++i) // 如果目前的點已經超過區域範圍了，則需要增加一個區域。 if (location[i] - location[s] > max_interval_width) { s = i; count++; // if (count > P) break; // 偷吃步 } return count; } // 從所有可能的答案中，找出正確答案。 int binary_search(int L, int R) { int ans = R; for (int M = (L+R)/2; L <= R; M = (L+R)/2) { // 計算分區數目，並驗證答案。 int p = interval_number(M); if (p <= P) // 答案剛好或太大，繼續檢查有沒有更好的答案 R = M-1, ans = M; else // 答案太小，不可能成為答案 L = M+1; } return ans; } void p_center() { int width = binary_search(0, location[N]); cout << "「最寬的區域」最窄為："; cout << float(width) / 2.0; }

UVa 714 11413 907

p-coverage problem

每個地點有半徑、支出、收入。連絡站建好後，涵蓋範圍為半徑、涵蓋到的地點有收入、沒涵蓋到的地點須支出，令總金額最高。

word wrap

一大段英文，適度換行，讓文字不超過紙張邊界。

為了美化版面，行末留白越少越好。

自訂一行留白代價，例如留白長度的平方。

統計各行留白代價，例如總和越小越好。

簡單起見，簡化細節：一、假設字母等寬。二、假設字母寬度是基本單位。三、假設頁面寬度是字母寬度的整數倍。

簡單起見，實施限制：一、單字不能從中切開換行。（實務上，多音節單字可以利用hyphen換行。）二、標點符號貼緊單字尾端。（實務上亦如是。）三、同行單字之間相隔一格空白。（實務上是行中均勻留白，而不是行末留白。）

現代文書編輯軟體退化成古代文字編輯器。

貪心法

留白代價是每單位均等，貪心法得以派上用場。

單字盡量往前擠，擠不下就換行。時間複雜度O(N)。

const int S = 30; // 單字數量。 int greedy_word_wrap() { int line = 0; int space = 0; for (int i=0; i<N; ++i) { // 單字比紙還寬，演算法立即結束。 if (a[i] > S) return -1; // 行末空白不足，需要換行。 if (a[i] + (space != S) > space) { line++; space = S; } // 單字擠入當前行數 space -= (a[i] + (space != S)); } return line; }

動態規劃

留白代價是特殊的公式，貪心法不管用。

事先計算總行數P，問題化作「所有單字分成P行」。問題等價於location allocation problem，留白代價宛如聯絡距離。

從最後一行的地方分開，化作兩串單字。開頭單字擠入前面幾行，尾端單字擠入最後一行，考慮所有可能的單字數量。

先枚舉行數，再枚舉最後一行有多少字數。時間複雜度O(N²P)。空間複雜度O(NP)。調整計算順序，空間複雜度降為O(N)。

f(p, i) =  min  { f(p-1, j) + cost(j+1, i) }
         j=0⋯i-1

where cost(a, b) = penalty(S - length(a, b))

f(p, i)：前i個單字擠入前p行的代價。
cost(a, b)：第i個單字到第j個單字，擠入同一行，其留白代價。
length(a, b)：文字長度，第i個單字到第j個單字。
penalty(x)：留白代價，當留白長度是x。（當x是負值，則代價無限大。）

const int N = 100; int a[N]; // 單字長度 int f[N]; // 表格 int c[N][N]; // 第i個單字到第j個單字，擠入同一行，其留白代價。 int cumulative_sum() { sum[0] = a[0]; for (int i=0; i<N; ++i) sum[i] = sum[i-1] + a[i]; } int length(int i, int j) { if (i == 0) return sum[j] + (j - 1); return sum[j] - sum[i-1] + (j - i); } int penalty(int x) { if (x < 0) return 1e9; return x * x; } int word_wrap() { // 預先計算單字總長度。 cumulative_sum(); // 預先計算留白代價 for (int i=0; i<N; i++) for (int j=i; j<N; j++) c[i][j] = penalty(S - length(i, j)); // 預先以貪心法找到總行數。 int P = greedy_word_wrap(); for (int p=0; p<P; p++) for (int j=N-1; j>=0; j--) { f[j] = min(f[j], c[0][j]); for (int i=1; i<=j; i++) f[j] = min(f[i-1], c[i][j]); } return f[N-1]; }

動態規劃：降維

要讓留白代價盡量小，就要讓行數盡量小。也就是說，總行數是明確數值，無須更動。

任意一串單字，總行數都是明確數值。遞迴公式得以省略行數。

換句話說。變數i的每一種數值，都可以求得明確數值p。有i就不必有p，於是省略變數p。

f(i) =  min  { f(j) + cost(j+1, i) }
      j=0⋯i-1

f(i)：前i個單字的留白代價總和。
cost(a, b)：第i個單字到第j個單字，擠入同一行，其留白代價。

時間複雜度O(N²)。空間複雜度O(N)。

所有N個單字通常無法擠入同一行。時間複雜度寫成O(N²)，其實不太精準。令最多連續M個單字擠入同一行，時間複雜度寫成O(NM)，變得比較精準。

UVa 709 848 400

動態規劃：unimodal function

留白代價恰是凸函數。兩個凸函數相加仍是凸函數。一個問題的候選解大小，恰巧形成凸函數（單峰函數）。各個問題的最佳解位置（山谷位置），恰巧遞增（往右移動）。用同一條掃描線尋找山谷。【尚待確認】

時間複雜度O(N)。空間複雜度O(N)。

動態規劃：totally monotone matrix

時間複雜度O(NlogN)。本題大可不必採用如此複雜的解法。

Zuma game【尚無正式名稱】

逐步消去一連串同色彩珠，找到步驟最少的消除方式。

據說時間複雜度O(N)。如果你會，麻煩教我。

問題分成兩種情況。一、可以分段處理：即是word wrap。二、無法分段處理（連續combo）：遞迴求解。

UVa 10559 11523