摘要: 經典的狀態壓縮DP。f[i][j]表示第i行，方格排布為二進制數j（第k位上為1表示凸出一個格子，為0表示不凸出）的方案數。用DFS進行狀態轉移。
如果行數比較多的話，可以用矩陣乘法優化。因為每行的狀態轉移都是相同的。設烈數為m，行數為n，可以做到O(2^(3m)logn)。

  閱讀全文      摘要: 經典的TSP問題變種。狀態為f[i][j][k]，表示經過二進制數i所指的哈密頓路（第bi位為1表示經過該點，為0表示不經過該點），倒數第二個點為j，最后一個點為k。.value表示最大權值，.num表示能走出最大權值的路徑數。若圖中k到p有邊，f[i][j][k]則轉移到f[i'][k][p]。i' == i | (1 << p)。

  閱讀全文      摘要:

  閱讀全文      摘要: int f[i][j]表示第i個字符到第j個字符需要添加的最少括號數。string ans[i][j] 表示第i個字符到第j個字符按照最優方案添加括號后的串。狀態轉移：1.f[i][j]由f[i + 1][j - 1]轉移來（通過兩端添括號() / [] ）。2.f[i][j]由f[i][k] + f[k + 1][j]轉移來（通過串合并）。答案是ans[0][len - 1]。

  閱讀全文      摘要: 枚舉矩形的上邊和下邊，花費O(n^2)，把問題轉化成一維的最大M子段和，做一個O(n)的DP。
  閱讀全文      摘要: pku 部分動態規劃題目列表

  閱讀全文      摘要: 題目給出 n 個矩形，要求它們的面積并。具體做法是離散化。先把 2n 個 x 坐標排序去重，然后再把所有水平線段（要記錄是矩形上邊還是下邊）按 y 坐標排序。最后對于每一小段區間 (x[i], x[i + 1]) 掃描所有的水平線段，求出這些水平線段在小區間內覆蓋的面積。總的時間復雜度是 O(n^2)。利用線段樹，可以優化到 O(nlogn)。

  閱讀全文      摘要: 求多邊形的核。用半平面交算法。

  閱讀全文      摘要: 強烈推薦此題！
先考察一下這個問題的性質。
性質1：任何一個圓都覆蓋了一個閉區域。
性質2：對于任意一個點，覆蓋它的最上面的那個圓，一定是可見的。
性質3：如果一個圓不可見（它被完全覆蓋），那么它的邊界是被完全覆蓋的。
性質4：n個圓最多有2(n-1)^2個交點，這些交點把n個圓分成最多2(n-1)^2條小圓弧。
性質5：對于每個小圓弧，要么它全被覆蓋，要么它全不被覆蓋。
根據性質1和性質2，問題轉化為恰當地找出一些點，對于每個點，把覆蓋它的最上面的圓標記為可見。
根據性質3，這些點一定在所有圓的邊界集合內。
根據性質5，所有小圓弧構成邊界集合。每個小圓弧上只要任意取一個點就能代表整個小圓弧（邊界）。不妨取中點。
至此得到算法：取所有小圓弧的中點，對每個點找到覆蓋它的最上面的圓。
根據性質4，最多取2(n-1)^2個點。對每個點找到覆蓋它的最上面的圓，需要O(n)次運算。總復雜度是O(n^3)。

  閱讀全文      摘要: Bless GCC!

  閱讀全文