[UVA] 10003 Cutting sticks

本來以為是單純的Huffman Encoding, WA! 因為Huffman Encoding只考慮棒子的長度，而題目有要求每根棒棒的起點需符合要求。這個陷阱搞了我三十分鍾，算是聰明反被聰明誤。

正確的作法是DP。想法如下：線段(x, y)的min cost可以表達成:
cost(x, y) = len(x, y) + min ( cost(x, z) + cost(z, y) ), where x < z < y。接下來，用2D array 建表即可 。唯一要注意的是diagonal DP的迴圈比較麻煩，第一次寫的時候犯了很多蠢錯。

[UVA] 10405 Longest Common Subsequence

可以說是DP的基本題了，無奈我還是繳了一個WA的過路費。Input不可以使用cin，否則space不能parse。請愛用getline

[UVA] 105 Skyline

經典的一題，搞了我整整一天。原本以為是很簡單的scan line題，結果發現充滿了陷阱。

[TODO]

Skyline有多種解法。最容易implement的方法是暴力建1D array,因為X軸是int 最大才10000，所以建個int[10001]，讀每個building update 每格田度，最後iterate array畫出輪廓即可。

另一種是方法是scan line，可以應付任意X軸範 圍，而且不限定於int。簡單來說，就是在每次遇到新建築時才畫輪廓。我們可以maintain一個heap，記出到目前為止，還沒遇到右端點的buildings。然後在遇到新building時，把heap中其右端點位於新building左端點左邊的building pop掉，然後畫輪廓即可。

這題的陷阱是複數building可能會有同樣的左端點，於是這樣一來必需要要用多餘的一個heap記住目前還沒被丟到heap的buildings, 而在遇到不一樣左端點的building時，把暫時heap的東西pop出灌到normal heap中。

[UVA] 10346 Peter Smokes

題目大義如下：

    Peter愛抽煙，他發現每抽K根煙，抽剩的K個煙屁股可以再捲成一根煙。今天有N根 煙，請問Peter總共可以抽幾次？

    這一題用simulation解非常簡單，原則上就是:
ANS = N + floor(N / K) + floor( N / K^2) + floor( N / K^3) + ....

   的數列和，而floor()是取round down的整數部份。O(logN)的效率還是不錯，不過經CL提點這題有O(1)解法，花了幾個小時狂試，發現居然真的有formula解:

ANS = N + floor( (N - 1) / (K - 1))

   我是作弊先把函數圖畫出來，再歸納出公式，所以並不是正統的邏輯推導得出的答案。我自己對這個公式的解釋是:

    N的部份就是原祖煙。而多出來的部份可以這樣想：抽完的N個煙屁股中，每K個煙屁股可以集中產生一支煙，然後丟棄K-1個煙屁股。這個集中 -- 回收 -- 丟棄的process可以移除 K - 1個煙屁股。這樣可以解釋分母 K - 1的由來，不過N - 1的部份我無法說明。後來經CL解答，才知道可以想成：把第一個煙屁股當做煙 斗，然後每 K - 1 根煙屁股可以跟煙斗合體再抽一次，抽完後剩下煙斗自己 ( K = >  1 )，所以總共有 1個煙斗，N - 1個煙屁股，每 K - 1個煙屁股可以再抽一次，而多抽的次數就是 (N - 1) / (K -1)。非常優雅的證明，也讓我見視到人跟神的差距。

[UVA] 108 Maximum Sum

寫了一堆I/O題後，在108就卡住了。O(n^4)雖然可能會過，不過一看就知道不是正解。

一維的maximum subarray是有線性解的(Kadane)，但是我推不出二維的線性解。原本想法是用DP，讓ary[i][j] 記住從它開始往右往下 展開最大的矩形，然後想辦法湊出ary[i+1][j+1] = function(ary[i-1][j-1], ary[i-1][j], ary[i][j-1])的形式，結果發現似乎不可能有O(n^2)的解><

投降後上網查了一下，發現可以用暴力+Kadane做到O(n^3)解。簡單來說，就是想辦法把2D array compact成一維，然後再找一維的最大值。實作就是把所有的列組合 i ~ j, i < j 列舉，然後累加，例如 Rowi ~ Rowj的累加一維矩陣就是就是 compact[k] =  array[i][k] + array[i+1][k] + .. + array[j][k]。接著把compact丟近Kadane，求最大值，收工。

教訓就是當1D變成多維時，可以使用暴力列舉製作出所有1D的組合再套用1D的DP解。