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

  閱讀全文      摘要: 經(jīng)典的TSP問題變種。狀態(tài)為f[i][j][k]，表示經(jīng)過二進制數(shù)i所指的哈密頓路（第bi位為1表示經(jīng)過該點，為0表示不經(jīng)過該點），倒數(shù)第二個點為j，最后一個點為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個字符到第j個字符需要添加的最少括號數(shù)。string ans[i][j] 表示第i個字符到第j個字符按照最優(yōu)方案添加括號后的串。狀態(tài)轉(zhuǎn)移：1.f[i][j]由f[i + 1][j - 1]轉(zhuǎn)移來（通過兩端添括號() / [] ）。2.f[i][j]由f[i][k] + f[k + 1][j]轉(zhuǎn)移來（通過串合并）。答案是ans[0][len - 1]。

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

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

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

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

  閱讀全文      摘要: Bless GCC!

  閱讀全文