7.26
最長公共子序列lcs, O(N^2)
f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1(if A_i==B_j)}
初始化f[_][0] = f[0][_] = 0
7.27
編輯距離edit, O(N^2)
f[i][j] = min(f[i][j-1] + 1, f[i-1][j] + 1, f[i-1][j-1] + !(A_i==A_j))
初始化f[i][0] = f[0][i] = i
*參考[這里]http://en.wikipedia.org/wiki/Levenshtein_distance
*狀態轉移過程中, 充分不一定最優, 必要才是最優; 事實上邊界條件總有其具體意義
*[相關]http://www.matrix67.com/blog/archives/333
最短回文串palindrome[poj 1159], O(N^2)
1.套用lcs, O(N^2), 60
f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1(if A_i==B_j)}
初始化f[_][0] = f[0][_] = 0, n - f[n][n]即為答案
*利用滾動數組優化, 空間復雜度O(N), 80
*關鍵語句k = 1 - k, 注意在內層循環外
2.套用edit, O(N^2), 30
f[i][j] = min(f[i][j-1] + 1, f[i-1][j] + 1, f[i-1][j-1] + 2*!(A_i==A_j))、
初始化f[i][0] = f[0][i] = i, f[n][n]/2即為答案
3.O(N^2), 30
f[i,j]表示將Ai..Aj變為回文串的最小代價，則
f[i][j] = f[i+1][j-1] (若Ai=Aj)
min(f[i+1][j],f[i][j-1])+1 （若Ai<>Aj）
4.利用位運算優化
http://www.csse.monash.edu.au/~lloyd/tildeStrings/Alignment/86.IPL.html
硬幣找零coin[完全背包], O(N^2)
f[j] = min(f[j], f[j-c[i]]+1)
初始化f[0] = 0, f[1..T] = INT_MAX
*注意下標非零 和 INT_MAX的溢出
7.28
導彈攔截missile[LIS + 二分], O(NlogN)
(1)二分查找O(logn)
f[i] = max(f[j] + 1) (j < i)
d[i] = min(f[k]) (f[k] == i)
易知d[i]單調, 因而可以利用二分查找降低復雜度, i最大值即LIS長度為t, 那么
i) f[i-1] < k <= f[i] (1 <= i <= t)
ii) 若k > 任意f[], 則f[t+1] = k;
iii) 若!k, 則f[1] = k;
*例子參見[這里]http://www.matrix67.com/blog/archives/112
[代碼實現]
//情況ii和iii需要單獨處理
x = 1; y = t;
while (x <= y){
m = (x + y)/2;
if (f[m-1] < k && k <= f[m]) break;//對于最長上升子序列和最長不下降子序列判定條件不明???
//if (f[m-1] < k && k <= f[m]) return m;
else if (k > f[m]) x = m + 1；
else y = m - 1;
//return x;
}
*利用注釋, 可以避免對情況ii的單獨處理LIS的方案, 記錄方案需要使用pre數組, 范例不知???
*需要注意的是, f數組給出的并非是一個
(2)最少鏈劃分 = 最長反鏈長度(關于偏序集, 參見《組合數學》P73)
[Dilworth定理]令（X,≤）是一個有限偏序集，并令m是反鏈的最大的大小。則X可以被劃分成m個但不能再少的鏈。
最長不下降子序列lis[LIS + 二分], O(NlogN)
對[1..k-1][k+1..n]兩個序列分別進行一次LIS即可.
*問題的關鍵之處在于第一次理解不徹底和浮躁, 以及對于困難程度的不合理估計.
7.29
加分二叉樹tree[區間 + 記錄方案], O(N^3), 20min
f[i][j] = max(f[i][k-1] * f[k+1][j] + A[k]) (i <= k <= j)
初始化f[i][i] = A[i], f[i+1][i] = 1
[記錄方案]pa[i][j] = k, 遞歸即可, [邊界]pa[i][j] == i 或者 j, 以及i == j的情況
整數劃分separate[區間 + 記錄方案], O(N^3), 2h
f[k][i]表示序列1..i分成k段的最大值
f[k][i] = max(f[k-1][j-1] * A[j][i])
pa[k][i] = j
初始化f[1][_] = A[1][_], 其他f[][] = -1
*注意等號情況同樣需要更新
if (f[K][i] <= f[K-1][k-1] * A[k][i])
f[K][i] = f[K-1][k-1] * A[k][i],
pa[K][i] = k; //記錄方案
*將[pa[k][i], i]加入答案, 遞歸[1, pa[k][i]-1], [邊界] k == 0
*在Win下使用long long占位符為"%I64d", 在Linux下占位符為"%lld", 考試中利用<fstream>避開占位符問題
凸多邊形的三角剖分division[區間]
f[i][j] = max{f[i][k] + f[k][j] + w(i, j, k)} (i < k < j)
初始化1<=i-j<=2的f只為0, 其他為-1
*表達式中同時出現long long和int的話, 會自動轉換為int
*只過了6個點, 原因不知 -> 數據錯誤, 最后4個點output一樣
*各種神牛們普遍指出沒有考慮i>j的情況 -> 怎么寫???
機器分配machine[區間], O(N^3)
f[i][j] = max(f[i-1][k] + A[i][j-k]) (0 <= k <= j)
初始化f[][] = 0, f[i][j] = max(f[i][j], A[i][j])
*注意讀題"第i個公司分配j臺機器的盈利", 不是分配第j臺機器的盈利
裝箱問題box[分組背包], O(N^2), 30min
f[i][j] = max{f[i-1][j], f[i-1][j-c[i][k]] + w[i][k]}
初始化f[][] = 0
*讀題時注意變量的對應關系
*注意本題中背包不一定要裝滿
7.31
最長前綴prefix[判斷性dp], O(kN), 70min
f[i] |= f[i - len[j]] & check(i - len[j] + 1, j) (1 <= i,j <= n)
初始化f[] = 0, check(x,y)表示主串[x,x+len[y]-1]和前綴y是否相同
*弄錯j和len[j], 注意方程的字母指代, 以及實現中的字符指針位置, 注意靜態查錯[30min]
*[8.4優化]把check函數直接寫在循環中, 如果f[i] == 1直接break -> 依舊超時三個點
*[8.5優化]i的上限為min(n, ans + 20), 更新f[i]的時候記錄ans即可 -> AC
8.1
關鍵子工程project[DAG最長路], 70min
f[i] = max(f[j] + w[i]) (G[j][i] == 1)
初始化f[i] = w[i]
記錄方案, 利用f[i] == w[i] + f[j] (G[j][i] == 1)
*利用定義求拓撲排序, 輸出方案可以利用隊列將遞歸轉化為迭代, 無解情況用flag標記(inq數組表示是否在隊列中)
*在紙上寫出關鍵部分的代碼, 兩倍行距(比如遞推或者記憶化函數, 輸出方案的函數)
8.2
三角蛋糕trigon[坐標dp], 130min
[做法1](需保留空格)
f_[i][j]表示以(i, j)為頂點的Rt△的最大邊長
對于倒三角形, 自右向左 f1[i][j] = min(f1[i+1][j], f1[i][j+1]) + 1
自左向右 f2[i][j] = min(f2[i+1][j], f2[i][j-1]) + 1
對于正三角形, 自右向左 f1[i][j] = min(f1[i-1][j], f1[i][j+1]) + 1
自左向右 f2[i][j] = min(f2[i-1][j], f2[i][j-1]) + 1
初始化, f[][] = 0(A[][] = '#'), f[][] = 1(A[][] = '-'); min(f1[i][j], f2[i][j])^2的最大值即為答案
[做法2](不需保留空格)
f[i][j]表示以(i, j)為頂點的△的最大高度
對于倒三角形, f[i][j] = min(f[i-1][j], f[i-1][j+1], f[i-1][j+2]) + 1
對于正三角形, f[i][j] = min(f[i+1][j], f[i+1][j-1], f[i+1][j-2]) + 1
初始化, f[][] = 0(A[][] = '#'), f[][] = 1(A[][] = '-'); min(f[i][j])^2即為答案
*輸入需保留空格, 卡了30min(排除ASCII為10或13的字符即可)
*沒有考慮正方向, 大約2h時對照std發現
*有兩個點數據錯誤, 對照std后發現std僅當橫坐標為奇數是考慮倒三角形, 橫坐標為偶數時考慮正三角形, 而題目中無此限制
*學習利用批處理對拍的寫法
@echo off
:again
gen
trigon
trigon_me
fc trigon.out trigon_me.out > nul
if not errorlevel 1 goto again
選課course[樹形dp]
[做法1]多叉轉二叉
f[i][j]表示以i為根節點的樹中, 選擇j門課
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-1] + i.v) (0<=k<j)
初始化f[][] = 0
*無法記錄方案 -> gXX表示比較困難
[做法2]泛化物品
??? -> 想撞墻 -> 需要學習
通向自由的鑰匙key[樹形dp], 150min, zoj 2280
f[i][j]表示以i為根節點的數, 花費能量為j時可以拿到的最多的鑰匙數
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-i.c] + i.v) (o<=k<=j-i.c)
初始化f[][] = -1, 邊界處理f[i][j] = 0(i<=0 || j<0)
*記錄各點鄰接矩陣, 利用dfs構造樹(注意處理后取消鄰接), 并多叉轉二叉 -> 30min
*對于f[i.r][j]不必在記憶化搜索函數中遍歷所有兄弟, 只遍歷最近的即可
*注意讀題, 出發點為1, i.c和i.v非負 -> 1.5min
*注意靜態查錯, 如記憶化搜索中dp(i, j)打成f(i, j)的情況
*覺得比較暈的時候等一下再調題, 可以先干點別的, 這樣可以減少時間的浪費
警衛安排security[樹形dp], 100min
[狀態]
f[i][0]表示以i為根節點, 并在i安排警衛的最小花費
f[i][1]表示以i為根節點, i的父節點已安排警衛的最小花費
f[i][2]表示以i為根節點, i的子節點已安排警衛的最小花費
[方程]
f[i][0] = Σmin(f[i.son][0], f[i.son][1], f[i.son][2]) + i.v
f[i][1] = Σmin{f[i.som][0], f[i.son][2]} (i不是樹的根節點)
f[i][2] = min{Σmin{f[i.son][0], f[i.son][2]}(i.son != k) + f[k = i.son][0]}
[初始化]
對于葉節點, f[i][0] = i.v, f[i][1] = 0, f[i][2] = i.v
對于其他值, f[][] = -1
*對于根節點的尋找, 利用prev[i]記錄i的前驅, 若!prev[i], 則i為樹根
*結合批處理和makedata以及小范圍暴力程序, 可以有效地避免各種錯誤及極端情況 -> 需要學習搜索
*對于這類題目, 思考的關鍵在于分類寫出方程, 并注意方程的邊界條件(類似:tyvj 沒有上司的舞會)
*對于樹形dp, 存在兩種類型; 一種是對于加權路徑長度限制, 另一種則是求加權最值
8.4
青蛙的煩惱frog[區間dp]
初看是最小生成樹問題, 但是此題有幾個特別的性質:
1.以1號荷葉為起點, 終點不定
2.遍歷荷葉的最短路徑是一條鏈
3.題目給出的坐標順序是一個順時針方向的多邊形
4.最短路徑不相交(畫一個四邊形, 利用三角形性質可以觀察到)
根據性質1和2, 容易得出O(N^3)的方程, 很明顯會超時
f[i][j] = min(f[k][j-1] + d[i][k]) (i!=k)
-f[i][j]表示以i為起點, 長度為j的最短路徑, 初始化f[i][1] = 0
進而考慮性質3和4, 因而對于點1, 只能選擇相鄰的點2和n, 可以得到O(N^2)的方程
f[i][j][0] = min{f[i+1][j-1][0] + d[i][i+1], f[i+1][j-1][1] + d[i][i+j-1]}
f[i][j][1] = min{f[i][j-1][1] + d[i+j-1][i+j-2], f[i][j-1][1] + d[i+j-1][i]}
-f[i][j][0]表示以i為起點, 長度為j的最短路徑, f[i][j][1]表示以i為終點, 長度為j的最短路徑, 初始化f[][1][] = 0
-一個實現上的小優化, 保證d[i][j](i<j)
*注意靜態查錯, 區別變量名, 思考算法的過程應該長于調試的過程
*修正了測試點6
火車進站train[線性dp], 70min
1.M <= 3 -> 可以分類討論
2.只存在一條軌道, M只能決定軌道的長度 -> 如果同時在軌道中, i在j前的必要條件是i.s<=j.s和i.t<=j.t
3.小站工作人員可以任意安排這些火車進站的先后排列 -> 記憶化搜索
4.小站允許幾輛火車同時進站或出站 -> 所有條件都可取等號
M = 1, f[i] = max(f[j] + 1) (i.t <= j.s)
M = 2, f[i][j] = max(f[j][k] + 1) (i.t <= k.s)
M = 3, f[i][j][k] = max(f[j][k][l] + 1) (i.t <= l.s)
初始化f = 0, 利用vis記錄是否計算過, 各下標互不相等
*枚舉過程中注意剪枝, 利用i!=j和i.s<=j.s,i.t<=j.t逐層處理即可
*[讀題]明確要求的是什么, 存在哪些條件, 寫list
*[未驗證]先對以進站時間為第一關鍵字, 出站時間為第二關鍵字進行快排, 然后直接遞推, 下標滿足i < j < k < l
快餐問題meal[資源分配(不妨認為是背包)dp + 貪心優化] -> 類似, usaco 3.4.4 rocker
f[k][i][j]表示k條生產線生產i個漢堡, j個薯條時生產飲料的最大值, p[k][i][j]表示第k條生產線, 其他同.
f[k][i][j] = max{f[k][i-ki][j-kj] + p[k][i][j]}
sum[i] = sum[i-1] + A[i]
初始化f[1][i][j] = p[1][i][j], f[2..n][i][j] = -1, 復雜度O(N*100^4)
幾個優化
1.注意到每種物品總數小于100, 最大產量的上限是lim = min(100/a, 100/b, 100/c, sum[n]/(a*p1+b*p2+c*p3))
2.為了避免數組越界, i的上限是min(lim*a, sum[n]/p1), j的上限min(lim*b, (A[k] - i*p1)/p2);
ki的上限min(i, A[k]/p1), kj的上限min(j, (A[k] - ki*p1)/p2) -> 對于逗號右邊, 其實就是ki*p1+kj*p2<=A[k]
3.將程序中的min/max用if語句替代
4.對于每一套生產線, 盡量成套生產
[反例]
1 1 1
2 3 7
3
15 16 17
貪心可得最大值為3, 實際上15 = 7 + 3 + 3 + 2, 16 = 7 + 3 + 2 + 2 + 2, 17 = 7 + 7 + 3, 最大值為4;
利用優化1和2可以過5個測試點, 優化3可以進一步優化時間常數, 利用優化4可以過9個測試點
AC程序參見[此文]http://hi.baidu.com/zijingningmeng/blog/item/2761617e2afe7ae32e73b3b3.html
*調試過程中的主要問題是邊界溢出(沒有區分是否計算過), 變量名寫錯
*網上有說法表示去掉每種物品的件數限制后, 題目變成網絡流 -> gXX證偽
*比賽的話, 不妨小數據(n<5)DP, 大數據(n>=5)貪心, 這樣應該可以得到超過一半的分數
卡車更新問題truck, O(N^2), 1h
f[i][k]表示第i年某車已使用了k年
f[i][k] = max{f(i+1, 1) + R[0] - U[0] - C[k], f(i+1, k+1) + R[k] - U[k]}
初始化f[][] = -1, 邊界條件f[i][k] = 0(i>N,k>K), 利用記憶化搜索實現
記錄方案利用bool型數組prev[i][j][k]記錄是否購買新車, 遞歸即可
*盡可能不換新車
*利用樣例構造樹, 寫出狀態即可得到方程
*測試點1存在等價方案, 已修正數據(可能需要Special Judge)
*f[i][j][k]中i和k可以唯一確定狀態, 因而可以去掉中間1維
選課course[樹形dp + 記錄方案], 多叉轉二叉實現
f[i][j]表示以i為根節點的樹中, 選擇j門課
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-1] + i.v) (0<=k<j)
初始化f[][] = 0
[記錄方案]
利用print(i, j)遞歸, vis[i][j]表示是否已遍歷, [邊界]i∈[1, m], j∈[1, n]
right[i][j]表示f[i][j]是否等于f[i.r][j]
prev[i][j] = k表示f[i][j]由f[i.l][k],f[i.r][j-k-1]推得, 這時需記錄p[i] = 1
從1到n判斷p[i]直接輸出即可.
8.5
廣場鋪磚問題floor[狀壓dp], 2h
f[i][S] = Σf[i-1][S'] (S由S'推得)
初始化f[1][0] = 1, f[h+1][0]即為答案
對于每個f[i-1][S']利用dfs(當前行i, 當前行狀態s1, 下一行狀態s2, 當前行指針k)尋找S
if(!(s2 & 1<<k) && !(s2 & 1<<(k+1)))
dp(i, s1, s2, k + 2);//存在連續兩個空位, 即橫放
dp(i, s1, s2 ^ (1<<(k)), k + 1);//對當前位取反, 即豎放
利用int保存每一位的擺放方式, 1表示當前行被上一行占用, 0表示當前行未被占用
[邊界]k = 0, 遞歸過程中k > w則退出
硬木地板floor2[狀壓dp]
f[i][S] = Σf[i-1][S'] (S由S'推得)
初始化f[1][0] = 1, f[h+1][0]即為答案
*實現無能, 最終放棄 -> 我應該去學位運算優化BFS -_-
*魚牛《狀態壓縮》理解不能, NOI導刊朱全民文章code不全.
*耗時最長的題目往往不是表面上的難題, 而是那些被簡單估計的難題