大家都能看懂吧，我相信大家都能看懂。
——多重背包
各位，這題妙不妙啊？妙不妙啊？？？
——bzoj1190
用什麼調什麼。
——記憶化搜尋
那實在是太蠢了。
——HDU3652
這位同志！！！
。。。
數位DP套路！絕對是套路！你把我這代碼背過就行啦。
——數位DP
朋友們，你們是在爬坡啊！等你們爬上來以後，你回頭看看，你會發現你走過的路是如此優美。
——ZHX
會的同學扣個 \(1\) ，或者可以扣個“我太強了”。
——樹形DP
背包DP
一般是給出一些“物品”，每個物品具有一些價值參數和花費參數，要求在滿足花費限制下最大化價值或者方案數。
01背包
- 給出 \(n\) 個物品，每個物品有 \(Vi\) 的價值和 \(Wi\) 的費用，我們總共有 \(m\) 塊錢，求最多能得到多少價值的物品。
\[f[i][j] = max \{f[i-1][j] , f[i][j-w[i]] + v[i] \}
\]
總體思路
設 \(dp[i][j]\) 表示前 \(i\) 個物品，用了 \(j\) 的花費得到的最大的價值。
\[dp[i][j] = max \{ dp[i-1][j] , dp[i-1][j-w[i]] + v[i] \}
代碼實作
memset(f, -0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= w[i]; j++)
f[i][j] = f[j - 1][j];
for (int j = w[i]; j <= m; j++)
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
}
更簡便更省空間更常用的寫法:
memset(f, -0x3f, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = m; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
多重背包
- 每一類物品可以無限選。
優化
- 貪心預處理:
- 對于所有 \(v[i] \geq v[j],w[i] \leq w[j]\) 的可以直接 \(pass\) 。
- 對于體積相同的隻留下價值大的。
- 對于随機資料效果更為顯著。
- 進制：
- 可以把 \(t[i]\) 拆成 \(1,2,4,8...t[i]-2^k\) ，這樣 \(k+1\) 組，這些組能拼成 \(0...t[i]\) 每一種情況，然後就把問題化簡成了 \(n \times \log(t[i])\) 個 01背包問題。
- 複雜度 \(O(n \times \log(t[i]) \times m )\)
- 單調隊列:
- 滑動視窗問題
一個細節~
求方案數
memset(f, -0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < w[i]; j++)
f[i][j] = f[j - 1][j];
for (int j = w[i]; j <= m; j++)
f[i][j] = max(f[i - 1][j], f[i][j - w[i]] + v[i])
}
memset(f, -0x3f, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= m; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
例題
1.BZOJ1190
P3188 [HNOI2007]夢幻島寶珠
2.把 \(n\) 劃分成不同 \(k\) 個正整數的方案數
設 \(f[i][j]\) 表示 把 \(i\) 劃分成 \(j\) 個數的方案數。
\[f[i][j] = f[i-1][j] + f[i-j][j-1]
3.BZOJ3612
狀态轉移的一點感觸
數位DP
經典數位DP是要求統計字元的個數
區間
和數字大小無關，隻和數字數量有關
BZOJ3209
樹形DP
樹上最大單獨集
一個大小為 \(n\) 的樹，求最大的獨立集
P1352 沒有上司的舞會
樹的直徑
給你一顆點數為 \(n\) 的樹，求這顆樹的直徑為多少。
即求樹上最遠兩點的距離
其他的一些簡單問題
1.tree china problem
給定一棵有 \(n\) 個點的樹，以及 \(m\) 條樹鍊，其中第 \(i\) 條樹鍊的價值為 \(w_i\) ，請選擇一些沒有公共點的樹鍊，使得價值和最大。
\(n,m \leq 100\)
考慮DP，
設 \(f[i]\) 為以 \(x\) 為根的子樹内選取不相交樹鍊的價值和的最大值，枚舉一條 \(LCA\) 為 \(i\) 的鍊 \((u,v,w)\) ,那麼目前方案的價值為 \(w\) 加上去除 \(u\) 到 \(v\)路徑上的點後深度最小的點的 \(f\) 的和。
時間複雜度 \(O ( m \times n)\)
樹鍊剖分優化可以做到 \(O(m \times \log (n)^2 )\)
2.BZOJ1864 三色二叉樹
P2585 [ZJOI2006]三色二叉樹
3.BZOJ4711 小奇挖礦
- 設 \(f[i][j]\) 表示 \(i\) 的子樹内所有點都确定了往哪送,并且 \(i\) 送到 \(j\),并且 \(j\) 還未建倉庫的最小代價。
樹上背包
簡化版
每個節點都有一個物品，價值是 \(v_i\)
-
設 \(f[i][j]\) 表示以 \(i\) 為根的子樹中選擇, \(i\) 強制選擇,選擇 \(j\) 個點的最大價值,轉移時每次将一個孩子暴力合并到父親上,合并就枚舉這個孩子内部選擇多少點即可。
\[f[i][j] = max \{ f[i][j-k] +f[son][k] | k = 0...(j-1) \}
就是枚舉 \(son\) 内選了多少點。
-
最樸素做法
設 \(f[i][j]\) 表示以 \(i\) 為根的子樹中選擇, \(i\) 強制選擇,重量為 \(j\) 的最大價值,轉移時每次将一個孩子暴力合并到父親上,合并就枚舉這個孩子内部選擇多少重量即可。
就是枚舉 \(son\) 内用了多少重量。
DFS序上做DP
- 在 \(dfs\) 序上 \(DP\) ，如果不選一個點，則跳過代表他的子樹的 \(dfs\) 上的連續一段。
- 設 \(f[i][j]\) 表示 \(dfs\) 序上第 \(i\) 個點到第 \(n\) 個點,選了 \(j\) 的重量得到的最大的價值時多少。\(i\) 既可以表示不選,也可以表示選。不選的話就跳過整個子樹。
- 設 \(t[i]\) 表示 \(dfs\) 序為 \(i\) 的點标号。
-
不選
\[f[i+size[t[i]]][j]
另一種奇妙的方法
經典題
一棵邊帶權值 \(n\) 個點的樹,求每個點在樹上的最遠距離。
- 套路方法:
- 隻需處理子樹的資訊就可以計算出全部答案,但是還有一些問題需要知道父親拿一枝的資訊。
- 兩遍 \(DFS\)
- 求出每個子樹内的資訊
void dfs_up(int u)
{
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
f[v][2] = max(f[u][2], f[v][0] + e[i].dis == f[u][0] ? f[u][1] : f[u][0]) + e[i].dis;
dfs_up(v);
}
}
\(f[u][0]\) : 是向下第一長的
\(f[u][1]\) : 是向下第二長的
\(f[u][2]\) : 向上最長的
每個點的答案就是以上三者的最大值。
基環樹（外向）
- 也就是環套樹
- 樹處理和環處理
處理方法
DFS找環
對于 \(DFS\) 找環，對這個基環樹做 \(DFS\) 周遊。
基環樹（内向）
- 首先是一個有向圖，構成類似基環樹的結構，每個點都隻有一個出度。
1.BZOJ1040
P2607 [ZJOI2008]騎士
- 讨厭關系的圖是個基環内向樹森林，求最大權獨立集
- 求最大獨立集内向和外向毫無差別，都是相鄰的不能選
- 找環 \(dfs\) 即可
BZOJ1791
未完待續。。。