7.13
p1057 金明的預算方案[分組背包], 1.5h
f[v] = max{f[v], f[v - c[i][j]] + w[i][j]}
*注意讀題，主件的編號和物品編號相同，這里調了1h
*注意逗號的使用
@Ural p1018 Binary Apple Tree[樹形], 1.5h{大量參考題解}
f[i][j] = max(f[tree[i].l][k] + f[tree[i].r][j-k-1] + tree[i].v)
*初始化中使用-1標記未計算(避免重復0)
*遞歸建樹 -> 尋找兒子的過程可利用鄰接表優(yōu)化[未驗證]
*記憶化搜索f[t][q]初始化為0, 根節(jié)點值最后計算, 注意特殊情況0
*特別注意, 把題目中的 邊權 轉換為 點權, 以及q的相關變化
7.15
#p1051 選課[樹形DP], 1.5h
f[i][j] = f[tree[i].r][j] (左子樹空)
f[tree[i].l][k]+f[tree[i].r][j-k-1]+tree[i].v (左子樹非空)
*多叉樹轉二叉樹 -> 左兒子, 右兄弟
if (!left[a]) tree[a].l = i;
else tree[left[a]].r = i;
left[a] = i;
**記憶化搜索過程為什么不能直接返回int -> 實驗證實會引起錯誤, 原因不明 -> 盲目合并語句所致
if (f[i][j] || i == 0 || j <= 0) return 0;
應為
if (i == 0 || j <= 0) return 0;
if (f[i][j]) return f[i][j] ;
-> 合并此類控制邊界語句應注意返回值
**泛化背包做法 http://archive.cnblogs.com/a/2091585/
p1087 sumsets[完全背包+統(tǒng)計方案數(shù)], 60min
f[i][j] = f[i-1][j] + f[i][j-c[i]] (f[0][0] = 1)
一開始盲目列表找遞推式, 嘗試無果. 后發(fā)現(xiàn)題目本意即完全背包問題, 2^k是物體, 實現(xiàn)時注意降維.
*統(tǒng)計方案總數(shù)問題遞推式中max改為+, 注意f[0] = 1
*此類問題注意高精度的實現(xiàn) 或者 mod(注意題目中要求, 如本題9位精度)
*另一種方程 f[i] = f[i-1] (i=2k+1) -> 已通過觀察得到
f[i-1] + f[i/2](i=2k) -> 動機是什么?
p1079 數(shù)字三角形3[坐標DP], 30min
f[i][j] = max(f[i+1][j], f[i+1][j+1]) + A[i][j] (0 < j <= i <= n/2)
通過分析可知, 指定點(n/2, n/2)前(i, i)必取, 而其后和一般數(shù)字三角做法相同, 終點為f[n/2][n/2]
故最終答案Σf(i,i)_(0 < i < n/2) + f[n/2][n/2]
*坐標問題注意分析起點和終點的要求
p1084 數(shù)字三角形4[坐標DP], 10min
(x, y)前: f1[i][j] = max(f1[i-1][j-1], f1[i-1][j]) + A[i][j] (0 < j <= i <= x)
(x, y)后: f2[i][j] = max(f2[i+1][j], f2[i+1][j+1]) + A[i][j]
分析可知, (x, y)前順推, 指定終點為(x, y), 起點必然為(1, 1), (x, y)后逆推, 指定終點為(x, y)
故最終答案為f1[x][y] + f2[x][y] - A[x][y]
p1076 數(shù)字三角形2[判定性DP], 30min
f[i][j][(k+A[i][j])%100] = f[i+1][j][k] | f[i+1][j+1][k]
通過增加維度轉化為判定性問題, 由于取模所以k的順序不確定, 因而用坐標來控制順序
7.16
#p1048 田忌賽馬[貪心 + DP], 1.5h
1.O(N + NlogN), [題解來自網(wǎng)絡]思想是這樣的, 先把各組馬的速度從大到小排序, 然后用田忌的馬順序與齊威王的馬比較
if（田忌的馬快）比較下一對馬；
else if（田忌的馬慢）用田忌最慢的馬和齊威王的這匹馬賽
else{
從未進行比賽的速度小的馬開始從后往前比
if（田忌的馬快） //這里是必須的，否則如果是90 73 71 和 90 70 70 ，那么沒有這個是
繼續(xù)往前比 //2-1,有了的話就是2+0，非常重要
else 用這匹馬和剛才跑平的齊威王的馬比
//總之原則就是如果這匹馬不能贏，就讓他和比他快很多的馬比，這樣保持速度較快的馬
}
*while循環(huán)條件, f1 <= r1
2.O(N^2 + NlogN), 來自:http://hi.baidu.com/lyltim/blog/item/57fccd1153ea851eb9127ba9.html
[貪心分析]
1、如果田忌剩下的馬中最強的馬都贏不了齊王剩下的最強的馬，那么應該用最差的一匹馬去輸給齊王最強的馬。
2、如果田忌剩下的馬中最強的馬可以贏齊王剩下的最強的馬，那就用這匹馬去贏齊王剩下的最強的馬。
3、如果田忌剩下的馬中最強的馬和齊王剩下的最強的馬打平的話，可以選擇打平或者用最差的馬輸?shù)舯荣悺?br />[DP做法]
f[i,j]=max{f[i-1,j]+g[n-(i-j)+1,i],f[i-1,j-1]+g[j,i]}
其中g[i,j]表示田忌的馬和齊王的馬分別按照由強到弱的順序排序之后，田忌的第i匹馬和齊王的第j匹馬賽跑所能取得的盈利
#p1402 烏龜棋[路徑DP], 1.5h
f[i][j][k][l] = max(f[i-1][j][k][l], f[i][j-1][k][l], f[i][j][k-1][l], f[i][j][k][l-1]) + A[i+2j+3k+4l+1]
以卡片數(shù)為階段, 狀態(tài)f[i][j][k][l]表示還剩下每種牌各多少張時得到的最大值, 注意起始位置
*卡了1h因為被05的過河和08的傳紙條限制思維, 認為以所在位置為階段, 想對空間降維
*[降維條件]狀態(tài)各維度存在等量關系, 因而可減少時間復雜度, 但是不能改變空間復雜度
#p1052 沒有上司的舞會[樹形DP], 1.5h
f[i][0] = ∑max{f[j][0], f[j][1]} (j∈i.son), i不參加
f[i][1] = ∑f[j][0] + tree[i].v (j∈i.son), i參加
[邊界]若i為葉節(jié)點, f[i][0] = 0, f[i][1] = tree[i].v
前半個小時寫完了多叉轉二叉, 證明了left[]的必要性.
*狀態(tài)設計問題: 沒有區(qū)分i參加和不參加的情況, 并認為f[i]由f[j](不取i, j是i的兒子)和f[k](取i, k是i的孫子)推得
*葉節(jié)點的初始化, 對于f[i][]求和而非取最大值, 選取根節(jié)點而非葉節(jié)點(需要兩個數(shù)組映射)
*由于30min時方程考慮不周, 導致多次修正, 因而卡了1h. 務必要先寫出正確方程.
7.18
p1134 CCR的中考之考前計劃[模擬], 50min
語文題, 題目描述問題很大, 浪費了0.5h, google了一個std之后得到正確題意. 題目是類似beads的模擬題, 將環(huán)從某處打斷, 使得兩端科目類型相同的天數(shù)最多.尋找相同科目的條件A[j+1] = 'w' || A[j+1] = A[i].
*環(huán)狀問題的處理方法: 2n-1, 在本題中雙方向同時進行不妨3n-2
#p1088 treat[區(qū)間DP], 20min
f[i][j] = max{f[i+1][j] + A[i] * (n+i-j), f[i][j-1] + A[j] * (n+i-j)} (0 < i < j <= n)
f[i][j]表示[i, j]未取時的最大值, 初始化f[i][j] = A[i] * n, 以長度l為階段, 故 j = i+l-1
*考慮第k次取數(shù), k = n - (i-j+1) + 1(包括這次), 昨天沒想到這點卡了很久
*在網(wǎng)上找到了另外一種設置狀態(tài)的方法, 設f[i][j]是取i個數(shù), 左邊取j個, 方程：
f[i][j] = max(f[i - 1][j - 1] + i * A[j], f[i - 1][j] + i * A[n - (i - 1 - j)])
-> 猜想動機: 存在等式 前 + 后 = 總數(shù), 狀態(tài)的設置都是為了描述著三個量.
agirnet[Krusal], 20min
復習并查集實現(xiàn)的Krusal
p1307 聯(lián)絡員[Krusal],50min
必選邊先使用set[find(e[i].u)] = find(e[i].v)合并, 并記錄權和, 然后按一般的Krusal做即可.
*使用stdlib.h的qsort間接排序失敗, 原因不知(20min)
*注意此時k++不能并入下一行語句中, 否則++k和k值不同導致輸入錯誤:
++k,
scanf("%d%d%d", &must[k].u, &must[k].v, &must[k].w);
7.20
p1113 魔族密碼[LIS模型], 40min, 6WA
f[i] = max{f[j] + 1} (A[j]為A[i]前綴, 1 <= j < i)
*注意最大值不一定在f[n]中, 需要對f[1] -> f[n]進行循環(huán)檢查, 卡了30min
p1187 小飛俠的游園方案[0/1背包], 15min
f[i][j] = max(f[i-1][j], f[i-1][j - c[i]] + w[i])
存在可能未裝滿的情況, 故循環(huán)檢查f[n][]即可
#p1190 積木城堡[背包DP], 1.5h, 6WA
f[k][j] = f[k][j - w[i]] (j - w[i] >= 0)
類似分組背包的做法, 記錄每組物品的所有可能值, 若f[1..k][V]同時為true, 則V為最值. 也可以在讀入時, 循環(huán)檢查每組物品的可能值.
*注意讀題, 尤其是各種數(shù)據(jù)范圍, 不要重復去年第二題!!!
*讀入時注意MAXn+1, 留意-1的情況; 顯然答案不會超過所有城堡的最小高度(而非最大).
*題目中并沒有強調按順序取積木, 因而一開始打了模擬, 之后手賤去Google. 對于這類問題, 在提交后若發(fā)現(xiàn)則應繼續(xù)思考. 此外不要給題目增加條件.
**注意這類確定各組物品所有可能值寫法 和 最優(yōu)值寫法的區(qū)別
*一組測試數(shù)據(jù):
5
87 76 65 54 32 21 23 -1
64 75 25 63 76 23 75 13 64 23 -1
09 78 76 46 32 45 23 -1
23 34 45 -1
12 34 23 -1
p1213 嵌套矩形[LIS模型/DAG最長路], 1h, 9WA
(1)f[i] = max(f[j] + 1) (rect[i]可嵌套rect[j])
*初始化f[] = 1; 初始化為0, 輸出+1會導致錯誤, 原因不知.
-> 另一種寫法(by Ylen): f[0] = 0, f[] = INT_MAX;
*注意題目沒有強調矩形間存在順序, 因而存在后效性. 易知面積小的矩形不會嵌套面積大的矩形, 因而以面積為關鍵字對rect進行間接排序.
(2)f[i] = max(f[j] + 1 | (i,j)∈G)
若rect[i]可嵌套rect[j], 則建立一條從i到j的邊, 求最長路即可