5.7
p1004 滑雪[2d最長下降子序列]
無思路.
p1005 采藥[簡單01背包], 調(diào)了1.5h
[spec,1d] f[j] = max{f[j], f[j - c[i]] + w[i]}, 能夠有效避免f[i][j]中i的指代問題
*2d寫法須注意f[i][j] = f[i-1][j]的值傳遞
for (i = 1; i <= n; i++)
for (j = T; j >= 1; j--)
if (j >= t[i])
f[i][j] = max(f[i - 1][j], f[i - 1][j - t[i]] + w[i]);
else f[i][j] = f[i - 1][j];
p1003 找啊找啊找GF[加強版01背包], 調(diào)了1h
讀題分析后發(fā)現(xiàn)是0/1背包模型, 時間需要單獨處理.(一開始認(rèn)為要記錄路徑, 其實不用這么麻煩)
f[m][r] = max{f[m][r], f[m - rmb[i]][r - rp[i]] + 1}
t[m][r] = max{t[m][r], f[m - rmb[i]][r - rp[i]] + time[i]}, 如果f[m]..和f[m-rmb[i]]..相等,注意更新t[m][r]
[補]寫rocker的時候想到一種方法，對于dp，維度往往是需要表示的量數(shù)-1，所以關(guān)于方程狀態(tài)的表示可以從時間復(fù)雜度、空間復(fù)雜度、需要表示的量數(shù)綜合考慮.此題中加上time的話，顯然爆時間，然后從這個方向思考方程.
p1015 公路乘車[線性dp]
f[i] = max{f[i - k] + A[k]} (1 <= k <= 10)
p1011 傳紙條[雙線程dp + 時間降維]
注意讀題, 題目中的來回等價為兩次同時的單向過程
f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2], f[x1-1][y1][x2][y2-1], f[x1][y1-1][x2][y2-1], f[x1][y1-1][x2-1][y2]}+A[x1][y1]+A[x2][y2]
注意每個數(shù)if and only if取一次, f[x1][y1][x2][y2] -= A[x1][y1](x1=x2&&y1=y2)
p1014 乘法游戲[區(qū)間dp]
無思路