IOI 2004 Phidias

由於有「一刀切」的條件, 很容易想到用 dp

dp[x][y] = 分割一 x*y 長方形最小的浪費空間

於是有

• dp[x][y] = 0 if size[x][y] exists
  
• dp[x][y] = min{ dp[x-i][y] | 0<i<x , dp[x][y-j] | 0<j<y }
  

但係我猜想, 其實會唔會每一次切都係切一些 plate size 的長度, 即

dp[x][y] = min{ dp[x-height[i]][y], dp[x][y-width[i]] }

最後發現是可行的
不過未 prove 到..