動態規劃

• [動態規劃]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 閱讀(1358) | 評論 (5)  編輯
• [動態規劃] pku1458 最長公共子序列      摘要: 最長公共子序列……想必很多人都知道吧……
  這里給出一個O(n^2)的算法，人人都會的。
  但是，我想說，我所知道的最好算法，是O(n^2 / logn)的。
  
    閱讀全文
  posted @ 2007-10-16 22:46 Felicia 閱讀(1412) | 評論 (4)  編輯
• [動態規劃]pku1080      摘要: 很簡單的DP，也是很基礎的DP。做法就不說啦：）
  
    閱讀全文
  posted @ 2007-10-12 22:25 Felicia 閱讀(1105) | 評論 (1)  編輯
• [動態規劃]pku1338      摘要: 非常經典的遞推計算。基本思想是設3個指針，分別表示3個素數乘到哪了，然后通過比較3個指針位置的遞推結果來確定下一個數是什么。
  具體實現見代碼。
  
    閱讀全文
  posted @ 2007-10-09 21:53 Felicia 閱讀(808) | 評論 (1)  編輯
• [動態規劃]pku3420      摘要: 經典題型。如果列數較少，就能用我們熟知的狀態壓縮DP解決。但現在列數有2^31。考慮到相鄰兩列之間狀態轉移規則是相同的，我們可以用矩陣表示這種轉移規則，而最后的結果就是求這個轉移矩陣的n次冪的左上角元素。
  
    閱讀全文
  posted @ 2007-10-08 09:19 Felicia 閱讀(1110) | 評論 (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 閱讀(800) | 評論 (1)  編輯
• [動態規劃]pku1179      摘要: 經典的DP，把環斷開，f[i][j][0]記錄i到j的最小值，f[i][j][1]記錄最大值，然后遞推計算。記錄最小值是因為兩個負數乘起來可能得到一個大的正數。
  
    閱讀全文
  posted @ 2007-10-05 16:47 Felicia 閱讀(613) | 評論 (0)  編輯
• [動態規劃]pku1189      摘要: 概率+DP，比較經典的題。按照遞推的方式計算概率。
  
    閱讀全文
  posted @ 2007-10-04 20:47 Felicia 閱讀(794) | 評論 (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 閱讀(1049) | 評論 (0)  編輯
• [動態規劃]pku1163      摘要: 今天郁悶了，貼個小代碼
  
    閱讀全文
  posted @ 2007-09-29 22:43 Felicia 閱讀(545) | 評論 (0)  編輯
• [動態規劃]動態規劃總結 by Amber      摘要: 動態規劃總結 by Amber
  
    閱讀全文
  posted @ 2007-09-29 20:25 Felicia 閱讀(3991) | 評論 (0)  編輯
• [動態規劃]pku3133      摘要: 強烈推薦此題！
  狀態壓縮DP的好題！
  分析見內
  
    閱讀全文
  posted @ 2007-09-24 21:12 Felicia 閱讀(1151) | 評論 (4)  編輯
• [動態規劃]pku1038      摘要: 經典的狀態壓縮DP，《算法藝術與信息學競賽》的例題。f[i][j]表示前i行，最后兩行狀態為二進制數j，嵌入的最多芯片數。第i行到第i+1行用DFS進行狀態轉移。
  由于第i+1行只和第i行有關，故可以用滾動數組優化。
  
    閱讀全文
  posted @ 2007-09-12 20:44 Felicia 閱讀(1556) | 評論 (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 閱讀(812) | 評論 (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 閱讀(678) | 評論 (0)  編輯

Full 動態規劃 Archive