[UVA] 125 Numbering Paths

大概是中年痴呆，這題居然花了我一整天...

這是一道DP題，非常classic的Floyd-Warshall題。F-W非常適合求all pair relation，有sub problem的DP題。想法如下：

dp[ i ] [ j ] [ k ]:  所有點 i 到點 j ，只經過點 0 ~ k 的路徑總合 

那麼：

dp[ i ] [ j ] [ k + 1] = dp[ i ] [ j ] [ k ] + 點 i 到點 j ，必包含點 k + 1的路徑數量

點 i 到點 j ，必包含點 k + 1的路徑數量即為：dp[ i ] [ k + 1] [ k ] * dp[ k + 1] [ j ] [ k ]

重新整理程式碼，出忽意料的簡單：

 

for k 

   for i

      for j 

          dp[ i ][ j ] += dp[ i ][ k + 1] * dp[ k + 1][ j ]

第二步是要消除 cycle。一開始想不到如何判斷一個點有沒有在cycle上。後來google後了解，如果點 i 在cycle上，那麼 dp[ i ][ i ] 會大於0，因為點 i 會有不為0的input edge 跟 output edge。然後注意不為0 的dp[ i ] [ k ] 和 dp[ k ][ i ]也要標成 -1。

[UVA] 164 String Computer

這個題目分成兩部份：第一部份，求兩個字串的minimum editing distance (即 Levenshtein Distance)，第二部份，求出step by step的edit 指令。

第一部份算是DP的老套了，蓋個二維DP table dp[i][j] 即可，i 為source string, j 為target string.。詳見wiki。

第二部份還蠻有意思，搞了我快三個小時。第一步是在建DP時要記住backtrace的path，然後拫據back trace的方向決定instruction的種類(-> 是back edge, 從終點返回起點)

  dp [i ] [ j]    ->    dp [ i - 1] [ j  - 1]   // CHANGE
                     ->    dp [ i ] [ j - 1 ]       //  INSERT
                     ->    dp [ i - 1 ] [ j ]       //  DELETE

第二步是決定instruction的值，包含char 與 position,
for dp [ i ] [ j ]:
                           char
  CHANGE:    target[ j - 1]
  INSERT        target[ j - 1]
  DELETE       source[ i - 1]

position是我認為這題最tricky的部份。由於instruction 會改變source string的長度，所以對dp[i][j]來說，editing position不會剛好在 i, 而是i + 字串長度累積變化量 (假設叫 delta) 。所以在建dp table時要同時紀錄每個cell的字串長度累積變化。


                           position
  CHANGE:    i + delta
  INSERT        i + delta + 1 (!)
  DELETE       i + delta

[UVA] 166 Making Change

錢幣組合一直是我的痛。我會DP，但是只要是錢幣題一定會搞我至少半天。這次也一樣。一個簡單的DP題，因為沒有check array index out of bound就搞了我一個小時。唉。

作法就是建兩個DP table，即金額對最少的錢幣數量。一個是店家用的shop_table，一個是顧客用的customer_table。注意店家的table 可以重復用，但是顧客的table每從都要regenerate，而且還 個別錢幣還有數量限制。

再由 Pay - Cost = Return
所以 coin_number[Cost] = min (customer_table[Pay] + shop_table[Pay - Cost]) Pay從Cost試到Cost + $1.95即可。

有用的測資：


2 2 2 2 2 1 4.05
2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
0 5 1 0 1 9 1.55
0 5 5 1 6 1 3.75
7 8 4 5 1 7 2
8 0 3 3 7 8 1.65
0 0 6 7 8 0 3.15
0 0 0 0 0 0

[UVA] 109 SCUD Busters

Convex Hull的經典題目。在一個二維的世界上，一個國家的國境是由一堆村莊組成的convex hull定義的。如果飛彈落在國境內，那就把國土面積累加到總焦土面積上。

題目本身沒有什麼陷阱，主要是練習computation geometry的幾個topic:

1. 給定一堆座標，求出convex hull
演算法筆記有非常細盡的介紹。我認為 Andrew's Monotone Chain 是最易懂，最好實作，完義不用考慮共線等boundary condition，效率也不差的作法。建議搭配wiki的pseudo code，理解這個方法的精髓。自己練習一下，

2. 求出convex hull 的面積
題目有給出公式。這裡有簡易的證明。

3. 判斷一個點是否落在一個convex hull裡面
我使用 equal area的作法。把convex hull的每個頂點跟測試點連起來，這樣會把convex hull分成n個小三角形。把所有小三角的面積相加，看是否等於convex hull的面積。相等即在內，反之在外。

另一個作法是sum angle, 即看看測試點與任二相鄰頂點的夾角總合是否為180度。是的話就在內。不過算角度要用除法，相比面積比較，可能會有floating precision的問題。

[UVA] 161 Traffic Lights

十足簡單的模擬題，但是依然吃了好幾個WA。題目不看清楚真的是我智商的問題了。
要點：
1. 開始的時間只要"任何一個燈"有變過紅燈即可
2. 05:00:00算成功


UVA forum 上的測資: