動態規劃

• [動態規劃]O(n^2 / logn)的LCS      摘要: 上次說，LCS有O(n^2 / logn)的解法。這個解法是在字符集不大的情況下，先預處理，再用位運算做狀態轉移。
  唐文斌曾經翻譯過一篇論文，專門討論這個問題。
  
  下面是練習題（n = 10000 的LCS）
  http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1210
  
  和我的解答
  
    閱讀全文
  posted @ 2007-10-19 16:56 Felicia 閱讀(1383) | 評論 (5)  編輯
• [動態規劃] pku1458 最長公共子序列      摘要: 最長公共子序列……想必很多人都知道吧……
  這里給出一個O(n^2)的算法，人人都會的。
  但是，我想說，我所知道的最好算法，是O(n^2 / logn)的。
  
    閱讀全文
  posted @ 2007-10-16 22:46 Felicia 閱讀(1435) | 評論 (4)  編輯
• [動態規劃]pku1080      摘要: 很簡單的DP，也是很基礎的DP。做法就不說啦：）
  
    閱讀全文
  posted @ 2007-10-12 22:25 Felicia 閱讀(1127) | 評論 (1)  編輯
• [動態規劃]pku1338      摘要: 非常經典的遞推計算。基本思想是設3個指針，分別表示3個素數乘到哪了，然后通過比較3個指針位置的遞推結果來確定下一個數是什么。
  具體實現見代碼。
  
    閱讀全文
  posted @ 2007-10-09 21:53 Felicia 閱讀(828) | 評論 (1)  編輯
• [動態規劃]pku3420      摘要: 經典題型。如果列數較少，就能用我們熟知的狀態壓縮DP解決。但現在列數有2^31。考慮到相鄰兩列之間狀態轉移規則是相同的，我們可以用矩陣表示這種轉移規則，而最后的結果就是求這個轉移矩陣的n次冪的左上角元素。
  
    閱讀全文
  posted @ 2007-10-08 09:19 Felicia 閱讀(1126) | 評論 (0)  編輯
• [動態規劃]pku1191      摘要: 不錯的DP題。狀態f[i][x1][y1][x2][y2]表示要把(x1,y1) -- (x2, y2) 分割成i塊所得到的最小平方和（平方和指的是每塊矩形的和的平方和）。然后根據水平和豎直切割進行狀態轉移。這樣計算出f[n][1][1][8][8]得到整個棋盤分割成n塊得到的最小平方和，然后代入均方差公式算得結果。
  
    閱讀全文
  posted @ 2007-10-08 09:12 Felicia 閱讀(819) | 評論 (1)  編輯
• [動態規劃]pku1179      摘要: 經典的DP，把環斷開，f[i][j][0]記錄i到j的最小值，f[i][j][1]記錄最大值，然后遞推計算。記錄最小值是因為兩個負數乘起來可能得到一個大的正數。
  
    閱讀全文
  posted @ 2007-10-05 16:47 Felicia 閱讀(630) | 評論 (0)  編輯
• [動態規劃]pku1189      摘要: 概率+DP，比較經典的題。按照遞推的方式計算概率。
  
    閱讀全文
  posted @ 2007-10-04 20:47 Felicia 閱讀(815) | 評論 (4)  編輯
• [動態規劃]pku1185      摘要: 經典的狀態壓縮DP，狀態是f[i][j]，表示第i行，以3進制j為狀態。j的位代表一個格子，只能是：0表示第i行和第i - 1行都沒有炮兵，1表示第i行沒有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS進行狀態轉移。一開始我做了超時，后來預處理了一下合法狀態，快了不少，才AC。
  
    閱讀全文
  posted @ 2007-09-30 22:09 Felicia 閱讀(1069) | 評論 (0)  編輯
• [動態規劃]pku1163      摘要: 今天郁悶了，貼個小代碼
  
    閱讀全文
  posted @ 2007-09-29 22:43 Felicia 閱讀(560) | 評論 (0)  編輯
• [動態規劃]動態規劃總結 by Amber      摘要: 動態規劃總結 by Amber
  
    閱讀全文
  posted @ 2007-09-29 20:25 Felicia 閱讀(4019) | 評論 (0)  編輯
• [動態規劃]pku3133      摘要: 強烈推薦此題！
  狀態壓縮DP的好題！
  分析見內
  
    閱讀全文
  posted @ 2007-09-24 21:12 Felicia 閱讀(1173) | 評論 (4)  編輯
• [動態規劃]pku1038      摘要: 經典的狀態壓縮DP，《算法藝術與信息學競賽》的例題。f[i][j]表示前i行，最后兩行狀態為二進制數j，嵌入的最多芯片數。第i行到第i+1行用DFS進行狀態轉移。
  由于第i+1行只和第i行有關，故可以用滾動數組優化。
  
    閱讀全文
  posted @ 2007-09-12 20:44 Felicia 閱讀(1581) | 評論 (3)  編輯
• [動態規劃]pku3375      摘要: A O(NM) dynamic programming algorithm is quite apparent after sorting the computers and network interfaces by their coordinates. Furthermore, in any optimized case, for each computer the difference between the the indices of the network interfaces matching to and closest to the computer is never larger than N. So the complexity could be reduced to O(N2)
  
  有很多細節不好考慮，應該是我的水平原因。最后我向updog要了數據才過的。而且代碼寫的不好。將就看一下吧。
  
    閱讀全文
  posted @ 2007-09-11 22:28 Felicia 閱讀(838) | 評論 (1)  編輯
• [動態規劃]pku1170      摘要: 呼~今天去學校啦！早上7點起床寫題，挑了個簡單題寫 ^_^
  這個是IOI95的DP題。用一個b位的6進制數i表示狀態。這個6進制數的每一位分別表示相應物品的數量。f[i]表示狀態i下的最小花費。同樣也可以用6進制數j表示優惠。那么，f[i]就能轉移到f[i - j]，如果優惠j可用的話。代價是使用優惠j時減少的花費。最后的答案就是min(f[i])，0 <= i <= start（start是初始狀態）。
  
    閱讀全文
  posted @ 2007-09-04 08:37 Felicia 閱讀(697) | 評論 (0)  編輯
• [動態規劃]pku1160      摘要: 先預處理，把第i個村子到第j個村子中，建一個郵局的最小代價算出來，存在min_cost[i][j]里。
  接下來就可以DP。設f[i][j]為前i個郵局，建在前j個村子的最小代價。那么f[i][j]可以轉移到f[i + 1][j + k]，(1 <= k 且 j + k <= n)，代價是min_cost[j + 1][j + k]。
  
    閱讀全文
  posted @ 2007-09-03 22:44 Felicia 閱讀(1526) | 評論 (3)  編輯
• [動態規劃]pku1088      摘要: 簡單的記憶化搜索。很早以前做的，代碼風格很亂。將就一下啦。
  
    閱讀全文
  posted @ 2007-09-02 20:02 Felicia 閱讀(944) | 評論 (5)  編輯
• [動態規劃]pku1737      摘要: 樓爺的題。遞推。f[n]表示n個結點的連通圖個數，則有遞推公式：
  
  void calc(int n)
  {
  f[n] = 0;
  for (int i = 1; i < n; i++)
  f[n] += f[i] * f[n - i] * (pow(i) - 1) * C(n - 2, i - 1);
  //pow(x) == 2^x
  }
  
  因為數據較多，所以預先算出f[1] -- f[50]，再輸出。要用高精度。我用了標程。
  
    閱讀全文
  posted @ 2007-09-02 13:53 Felicia 閱讀(789) | 評論 (6)  編輯
• [動態規劃]pku1946      摘要: 首先明確一點：最優解必為奶牛1..n-1輪流領跑，奶牛n撞線。且跑了x圈后，未領跑過的奶牛都耗費了x的體力。
  設f[i][j][k]表示前i-1頭奶牛已領跑，現在由第i頭奶牛領跑，一共跑了j圈，奶牛i耗費了k的體力。
  則f[i][j][k]可以轉移到f[i][j + p][k + p^2]（耗費1分鐘，奶牛i以p圈/分鐘的速度繼續領跑），也可轉移到f[i + 1][j][j]（換成奶牛i + 1領跑，不耗費時間）。
  時間復雜度為O(nde^2.5)。
  
    閱讀全文
  posted @ 2007-09-01 11:42 Felicia 閱讀(507) | 評論 (1)  編輯
• [動態規劃]pku1947      摘要: 推薦此題。基礎樹型DP。
  f[x][i](1 <= i <= p)表示以x為根的子樹，變成剩下i個點的子樹，且剩余子樹包含根結點，需要去掉的最少邊數。
  那么父結點的f值可以由它所有的兒子的f值做背包得到。
  最后的答案是min(min(f[i][p]) + 1 (2 <= i <= n), f[1][p])
  
    閱讀全文
  posted @ 2007-08-31 18:27 Felicia 閱讀(879) | 評論 (0)  編輯
• [動態規劃]pku1848      摘要: 強烈推薦此題。樹型DP。
  分析較長且帶有圖示，請閱讀全文。
  
    閱讀全文
  posted @ 2007-08-30 21:47 Felicia 閱讀(1058) | 評論 (4)  編輯
• [動態規劃]pku1112      摘要: 強烈推薦此題。圖論和DP結合。
  分析較長，請閱讀全文。
  
    閱讀全文
  posted @ 2007-08-29 17:15 Felicia 閱讀(938) | 評論 (4)  編輯
• [動態規劃]pku2411      摘要: 經典的狀態壓縮DP。f[i][j]表示第i行，方格排布為二進制數j（第k位上為1表示凸出一個格子，為0表示不凸出）的方案數。用DFS進行狀態轉移。
  如果行數比較多的話，可以用矩陣乘法優化。因為每行的狀態轉移都是相同的。設烈數為m，行數為n，可以做到O(2^(3m)logn)。
  
    閱讀全文
  posted @ 2007-08-28 21:03 Felicia 閱讀(1440) | 評論 (12)  編輯
• [動態規劃]pku2288      摘要: 經典的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)。
  
    閱讀全文
  posted @ 2007-08-28 20:47 Felicia 閱讀(847) | 評論 (2)  編輯
• [動態規劃]pku1141      摘要: 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]。
  
    閱讀全文
  posted @ 2007-08-27 15:55 Felicia 閱讀(1256) | 評論 (3)  編輯
• [動態規劃]pku1050      摘要: 枚舉矩形的上邊和下邊，花費O(n^2)，把問題轉化成一維的最大M子段和，做一個O(n)的DP。
    閱讀全文
  posted @ 2007-08-26 13:51 Felicia 閱讀(1041) | 評論 (6)  編輯
• [動態規劃]pku 部分動態規劃題目列表      摘要: pku 部分動態規劃題目列表
  
    閱讀全文
  posted @ 2007-08-26 11:52 Felicia 閱讀(6613) | 評論 (5)  編輯
• [動態規劃]pku3345      摘要: 建立一個虛點（權為無窮大），從它到每個入度為 0 的點都連一條邊，然后做樹型DP。
  先遞歸算出子結點的 f 值，然后用背包的方法計算父結點的 f 值。
  
    閱讀全文
  posted @ 2007-08-15 18:42 Felicia 閱讀(641) | 評論 (0)  編輯