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

• [動態(tài)規(guī)劃]O(n^2 / logn)的LCS      摘要: 上次說，LCS有O(n^2 / logn)的解法。這個解法是在字符集不大的情況下，先預(yù)處理，再用位運算做狀態(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 閱讀(1374) | 評論 (5)  編輯
• [動態(tài)規(guī)劃] pku1458 最長公共子序列      摘要: 最長公共子序列……想必很多人都知道吧……
  這里給出一個O(n^2)的算法，人人都會的。
  但是，我想說，我所知道的最好算法，是O(n^2 / logn)的。
  
    閱讀全文
  posted @ 2007-10-16 22:46 Felicia 閱讀(1423) | 評論 (4)  編輯
• [動態(tài)規(guī)劃]pku1080      摘要: 很簡單的DP，也是很基礎(chǔ)的DP。做法就不說啦：）
  
    閱讀全文
  posted @ 2007-10-12 22:25 Felicia 閱讀(1115) | 評論 (1)  編輯
• [動態(tài)規(guī)劃]pku1338      摘要: 非常經(jīng)典的遞推計算。基本思想是設(shè)3個指針，分別表示3個素數(shù)乘到哪了，然后通過比較3個指針位置的遞推結(jié)果來確定下一個數(shù)是什么。
  具體實現(xiàn)見代碼。
  
    閱讀全文
  posted @ 2007-10-09 21:53 Felicia 閱讀(820) | 評論 (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 閱讀(1119) | 評論 (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 閱讀(809) | 評論 (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 閱讀(622) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]pku1189      摘要: 概率+DP，比較經(jīng)典的題。按照遞推的方式計算概率。
  
    閱讀全文
  posted @ 2007-10-04 20:47 Felicia 閱讀(803) | 評論 (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 閱讀(1058) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]pku1163      摘要: 今天郁悶了，貼個小代碼
  
    閱讀全文
  posted @ 2007-09-29 22:43 Felicia 閱讀(552) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]動態(tài)規(guī)劃總結(jié) by Amber      摘要: 動態(tài)規(guī)劃總結(jié) by Amber
  
    閱讀全文
  posted @ 2007-09-29 20:25 Felicia 閱讀(4003) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]pku3133      摘要: 強烈推薦此題！
  狀態(tài)壓縮DP的好題！
  分析見內(nèi)
  
    閱讀全文
  posted @ 2007-09-24 21:12 Felicia 閱讀(1162) | 評論 (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 閱讀(1568) | 評論 (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 閱讀(825) | 評論 (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 閱讀(687) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]pku1160      摘要: 先預(yù)處理，把第i個村子到第j個村子中，建一個郵局的最小代價算出來，存在min_cost[i][j]里。
  接下來就可以DP。設(shè)f[i][j]為前i個郵局，建在前j個村子的最小代價。那么f[i][j]可以轉(zhuǎn)移到f[i + 1][j + k]，(1 <= k 且 j + k <= n)，代價是min_cost[j + 1][j + k]。
  
    閱讀全文
  posted @ 2007-09-03 22:44 Felicia 閱讀(1519) | 評論 (3)  編輯
• [動態(tài)規(guī)劃]pku1088      摘要: 簡單的記憶化搜索。很早以前做的，代碼風(fēng)格很亂。將就一下啦。
  
    閱讀全文
  posted @ 2007-09-02 20:02 Felicia 閱讀(932) | 評論 (5)  編輯
• [動態(tài)規(guī)劃]pku1737      摘要: 樓爺?shù)念}。遞推。f[n]表示n個結(jié)點的連通圖個數(shù)，則有遞推公式：
  
  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
  }
  
  因為數(shù)據(jù)較多，所以預(yù)先算出f[1] -- f[50]，再輸出。要用高精度。我用了標(biāo)程。
  
    閱讀全文
  posted @ 2007-09-02 13:53 Felicia 閱讀(779) | 評論 (6)  編輯
• [動態(tài)規(guī)劃]pku1946      摘要: 首先明確一點：最優(yōu)解必為奶牛1..n-1輪流領(lǐng)跑，奶牛n撞線。且跑了x圈后，未領(lǐng)跑過的奶牛都耗費了x的體力。
  設(shè)f[i][j][k]表示前i-1頭奶牛已領(lǐng)跑，現(xiàn)在由第i頭奶牛領(lǐng)跑，一共跑了j圈，奶牛i耗費了k的體力。
  則f[i][j][k]可以轉(zhuǎn)移到f[i][j + p][k + p^2]（耗費1分鐘，奶牛i以p圈/分鐘的速度繼續(xù)領(lǐng)跑），也可轉(zhuǎn)移到f[i + 1][j][j]（換成奶牛i + 1領(lǐng)跑，不耗費時間）。
  時間復(fù)雜度為O(nde^2.5)。
  
    閱讀全文
  posted @ 2007-09-01 11:42 Felicia 閱讀(496) | 評論 (1)  編輯
• [動態(tài)規(guī)劃]pku1947      摘要: 推薦此題。基礎(chǔ)樹型DP。
  f[x][i](1 <= i <= p)表示以x為根的子樹，變成剩下i個點的子樹，且剩余子樹包含根結(jié)點，需要去掉的最少邊數(shù)。
  那么父結(jié)點的f值可以由它所有的兒子的f值做背包得到。
  最后的答案是min(min(f[i][p]) + 1 (2 <= i <= n), f[1][p])
  
    閱讀全文
  posted @ 2007-08-31 18:27 Felicia 閱讀(872) | 評論 (0)  編輯
• [動態(tài)規(guī)劃]pku1848      摘要: 強烈推薦此題。樹型DP。
  分析較長且?guī)в袌D示，請閱讀全文。
  
    閱讀全文
  posted @ 2007-08-30 21:47 Felicia 閱讀(1049) | 評論 (4)  編輯
• [動態(tài)規(guī)劃]pku1112      摘要: 強烈推薦此題。圖論和DP結(jié)合。
  分析較長，請閱讀全文。
  
    閱讀全文
  posted @ 2007-08-29 17:15 Felicia 閱讀(925) | 評論 (4)  編輯
• [動態(tài)規(guī)劃]pku2411      摘要: 經(jīng)典的狀態(tài)壓縮DP。f[i][j]表示第i行，方格排布為二進(jìn)制數(shù)j（第k位上為1表示凸出一個格子，為0表示不凸出）的方案數(shù)。用DFS進(jìn)行狀態(tài)轉(zhuǎn)移。
  如果行數(shù)比較多的話，可以用矩陣乘法優(yōu)化。因為每行的狀態(tài)轉(zhuǎn)移都是相同的。設(shè)烈數(shù)為m，行數(shù)為n，可以做到O(2^(3m)logn)。
  
    閱讀全文
  posted @ 2007-08-28 21:03 Felicia 閱讀(1426) | 評論 (12)  編輯
• [動態(tài)規(guī)劃]pku2288      摘要: 經(jīng)典的TSP問題變種。狀態(tài)為f[i][j][k]，表示經(jīng)過二進(jìn)制數(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)。
  
    閱讀全文
  posted @ 2007-08-28 20:47 Felicia 閱讀(838) | 評論 (2)  編輯
• [動態(tài)規(guī)劃]pku1141      摘要: 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]。
  
    閱讀全文
  posted @ 2007-08-27 15:55 Felicia 閱讀(1245) | 評論 (3)  編輯
• [動態(tài)規(guī)劃]pku1050      摘要: 枚舉矩形的上邊和下邊，花費O(n^2)，把問題轉(zhuǎn)化成一維的最大M子段和，做一個O(n)的DP。
    閱讀全文
  posted @ 2007-08-26 13:51 Felicia 閱讀(1028) | 評論 (6)  編輯
• [動態(tài)規(guī)劃]pku 部分動態(tài)規(guī)劃題目列表      摘要: pku 部分動態(tài)規(guī)劃題目列表
  
    閱讀全文
  posted @ 2007-08-26 11:52 Felicia 閱讀(6600) | 評論 (5)  編輯
• [動態(tài)規(guī)劃]pku3345      摘要: 建立一個虛點（權(quán)為無窮大），從它到每個入度為 0 的點都連一條邊，然后做樹型DP。
  先遞歸算出子結(jié)點的 f 值，然后用背包的方法計算父結(jié)點的 f 值。
  
    閱讀全文
  posted @ 2007-08-15 18:42 Felicia 閱讀(632) | 評論 (0)  編輯