大家都能看懂吧，我相信大家都能看懂。
——多重背包
各位，这题妙不妙啊？妙不妙啊？？？
——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
未完待续。。。