動態(tài)規(guī)劃

• [動態(tài)規(guī)劃]O(n^2 / logn)的LCS      摘要: 上次說，LCS有O(n^2 / logn)的解法。這個解法是在字符集不大的情況下，先預(yù)處理，再用位運(yùn)算做狀態(tài)轉(zhuǎn)移。
  唐文斌曾經(jīng)翻譯過一篇論文，專門討論這個問題。
  
  下面是練習(xí)題（n = 10000 的LCS）
  http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1210
  
  和我的解答
  
    閱讀全文
  posted @ 2007-10-19 16:56 Felicia 閱讀(1392) | 評論 (5)  編輯
• [動態(tài)規(guī)劃] pku1458 最長公共子序列      摘要: 最長公共子序列……想必很多人都知道吧……
  這里給出一個O(n^2)的算法，人人都會的。
  但是，我想說，我所知道的最好算法，是O(n^2 / logn)的。
  
    閱讀全文
  posted @ 2007-10-16 22:46 Felicia 閱讀(1443) | 評論 (4)  編輯
• [動態(tài)規(guī)劃]pku1080      摘要: 很簡單的DP，也是很基礎(chǔ)的DP。做法就不說啦：）
  
    閱讀全文
  posted @ 2007-10-12 22:25 Felicia 閱讀(1134) | 評論 (1)  編輯
• [動態(tài)規(guī)劃]pku1338      摘要: 非常經(jīng)典的遞推計算。基本思想是設(shè)3個指針，分別表示3個素數(shù)乘到哪了，然后通過比較3個指針位置的遞推結(jié)果來確定下一個數(shù)是什么。
  具體實現(xiàn)見代碼。
  
    閱讀全文
  posted @ 2007-10-09 21:53 Felicia 閱讀(836) | 評論 (1)  編輯
• [動態(tài)規(guī)劃]pku3420      摘要: 經(jīng)典題型。如果列數(shù)較少，就能用我們熟知的狀態(tài)壓縮DP解決。但現(xiàn)在列數(shù)有2^31。考慮到相鄰兩列之間狀態(tài)轉(zhuǎn)移規(guī)則是相同的，我們可以用矩陣表示這種轉(zhuǎn)移規(guī)則，而最后的結(jié)果就是求這個轉(zhuǎn)移矩陣的n次冪的左上角元素。
  
    閱讀全文
  posted @ 2007-10-08 09:19 Felicia 閱讀(1133) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]pku1191      摘要: 不錯的DP題。狀態(tài)f[i][x1][y1][x2][y2]表示要把(x1,y1) -- (x2, y2) 分割成i塊所得到的最小平方和（平方和指的是每塊矩形的和的平方和）。然后根據(jù)水平和豎直切割進(jìn)行狀態(tài)轉(zhuǎn)移。這樣計算出f[n][1][1][8][8]得到整個棋盤分割成n塊得到的最小平方和，然后代入均方差公式算得結(jié)果。
  
    閱讀全文
  posted @ 2007-10-08 09:12 Felicia 閱讀(832) | 評論 (1)  編輯
• [動態(tài)規(guī)劃]pku1179      摘要: 經(jīng)典的DP，把環(huán)斷開，f[i][j][0]記錄i到j(luò)的最小值，f[i][j][1]記錄最大值，然后遞推計算。記錄最小值是因為兩個負(fù)數(shù)乘起來可能得到一個大的正數(shù)。
  
    閱讀全文
  posted @ 2007-10-05 16:47 Felicia 閱讀(636) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]pku1189      摘要: 概率+DP，比較經(jīng)典的題。按照遞推的方式計算概率。
  
    閱讀全文
  posted @ 2007-10-04 20:47 Felicia 閱讀(822) | 評論 (4)  編輯
• [動態(tài)規(guī)劃]pku1185      摘要: 經(jīng)典的狀態(tài)壓縮DP，狀態(tài)是f[i][j]，表示第i行，以3進(jìn)制j為狀態(tài)。j的位代表一個格子，只能是：0表示第i行和第i - 1行都沒有炮兵，1表示第i行沒有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS進(jìn)行狀態(tài)轉(zhuǎn)移。一開始我做了超時，后來預(yù)處理了一下合法狀態(tài)，快了不少，才AC。
  
    閱讀全文
  posted @ 2007-09-30 22:09 Felicia 閱讀(1073) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]pku1163      摘要: 今天郁悶了，貼個小代碼
  
    閱讀全文
  posted @ 2007-09-29 22:43 Felicia 閱讀(565) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]動態(tài)規(guī)劃總結(jié) by Amber      摘要: 動態(tài)規(guī)劃總結(jié) by Amber
  
    閱讀全文
  posted @ 2007-09-29 20:25 Felicia 閱讀(4029) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]pku3133      摘要: 強(qiáng)烈推薦此題！
  狀態(tài)壓縮DP的好題！
  分析見內(nèi)
  
    閱讀全文
  posted @ 2007-09-24 21:12 Felicia 閱讀(1183) | 評論 (4)  編輯
• [動態(tài)規(guī)劃]pku1038      摘要: 經(jīng)典的狀態(tài)壓縮DP，《算法藝術(shù)與信息學(xué)競賽》的例題。f[i][j]表示前i行，最后兩行狀態(tài)為二進(jìn)制數(shù)j，嵌入的最多芯片數(shù)。第i行到第i+1行用DFS進(jìn)行狀態(tài)轉(zhuǎn)移。
  由于第i+1行只和第i行有關(guān)，故可以用滾動數(shù)組優(yōu)化。
  
    閱讀全文
  posted @ 2007-09-12 20:44 Felicia 閱讀(1591) | 評論 (3)  編輯
• [動態(tài)規(guī)劃]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)
  
  有很多細(xì)節(jié)不好考慮，應(yīng)該是我的水平原因。最后我向updog要了數(shù)據(jù)才過的。而且代碼寫的不好。將就看一下吧。
  
    閱讀全文
  posted @ 2007-09-11 22:28 Felicia 閱讀(846) | 評論 (1)  編輯
• [動態(tài)規(guī)劃]pku1170      摘要: 呼~今天去學(xué)校啦！早上7點起床寫題，挑了個簡單題寫 ^_^
  這個是IOI95的DP題。用一個b位的6進(jìn)制數(shù)i表示狀態(tài)。這個6進(jìn)制數(shù)的每一位分別表示相應(yīng)物品的數(shù)量。f[i]表示狀態(tài)i下的最小花費。同樣也可以用6進(jìn)制數(shù)j表示優(yōu)惠。那么，f[i]就能轉(zhuǎn)移到f[i - j]，如果優(yōu)惠j可用的話。代價是使用優(yōu)惠j時減少的花費。最后的答案就是min(f[i])，0 <= i <= start（start是初始狀態(tài)）。
  
    閱讀全文
  posted @ 2007-09-04 08:37 Felicia 閱讀(700) | 評論 (0)  編輯

Full 動態(tài)規(guī)劃 Archive