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