摘要: 經(jīng)典的狀態(tài)壓縮DP。f[i][j]表示第i行，方格排布為二進(jìn)制數(shù)j（第k位上為1表示凸出一個(gè)格子，為0表示不凸出）的方案數(shù)。用DFS進(jìn)行狀態(tài)轉(zhuǎn)移。
如果行數(shù)比較多的話，可以用矩陣乘法優(yōu)化。因?yàn)槊啃械臓顟B(tài)轉(zhuǎn)移都是相同的。設(shè)烈數(shù)為m，行數(shù)為n，可以做到O(2^(3m)logn)。

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

  閱讀全文      摘要:

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

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

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

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

  閱讀全文      摘要: 強(qiáng)烈推薦此題！
先考察一下這個(gè)問題的性質(zhì)。
性質(zhì)1：任何一個(gè)圓都覆蓋了一個(gè)閉區(qū)域。
性質(zhì)2：對(duì)于任意一個(gè)點(diǎn)，覆蓋它的最上面的那個(gè)圓，一定是可見的。
性質(zhì)3：如果一個(gè)圓不可見（它被完全覆蓋），那么它的邊界是被完全覆蓋的。
性質(zhì)4：n個(gè)圓最多有2(n-1)^2個(gè)交點(diǎn)，這些交點(diǎn)把n個(gè)圓分成最多2(n-1)^2條小圓弧。
性質(zhì)5：對(duì)于每個(gè)小圓弧，要么它全被覆蓋，要么它全不被覆蓋。
根據(jù)性質(zhì)1和性質(zhì)2，問題轉(zhuǎn)化為恰當(dāng)?shù)卣页鲆恍c(diǎn)，對(duì)于每個(gè)點(diǎn)，把覆蓋它的最上面的圓標(biāo)記為可見。
根據(jù)性質(zhì)3，這些點(diǎn)一定在所有圓的邊界集合內(nèi)。
根據(jù)性質(zhì)5，所有小圓弧構(gòu)成邊界集合。每個(gè)小圓弧上只要任意取一個(gè)點(diǎn)就能代表整個(gè)小圓弧（邊界）。不妨取中點(diǎn)。
至此得到算法：取所有小圓弧的中點(diǎn)，對(duì)每個(gè)點(diǎn)找到覆蓋它的最上面的圓。
根據(jù)性質(zhì)4，最多取2(n-1)^2個(gè)點(diǎn)。對(duì)每個(gè)點(diǎn)找到覆蓋它的最上面的圓，需要O(n)次運(yùn)算。總復(fù)雜度是O(n^3)。

  閱讀全文      摘要: Bless GCC!

  閱讀全文