奇怪的DP
P5975 [CEOI2009] photo
很抽象的题
path
给定一个 \(n\times m\) 的矩形，从左下角 \((n,1)\) 出发，可以向右转或向前走，障碍物和走过的格子不能走，求走到 \((s,t)\) 的方案数，答案模 \(k\)
\(1\leq n,m\leq 40\)，\(k\leq 10^9\)
只有方向不可做
设 \(f[a][b][x][y][0\cdots 3]\) 表示矩形 \((a,b,x,y)\) 从左上角、左下角、右上角、右下角进入的方案数。枚举走了多少步后再拐弯再进行转移
Paint Pearls
\(n\) 个位置，每个位置有 \(1\) 个目标颜色。每次选择一个区间，将区间所有的位置全部改成目标颜色。设区间内不同颜色的数量为 \(x\)，则操作的代价为 \(x^2\)，求最小代价
\(1\leq n\leq 5\times 10^4\)
设 \(f[i]\) 表示 \(1\) 到 \(i\) 的最小代价
下界是 \(n\)（一个个改）。因此若区间内不同颜色的数量超过 \(\sqrt{n}\)，则不会直接操作。
记录当前位置往前 \(\sqrt{n}\) 种颜色及其对应位置即可
Data Structure You've Never Heard Of
给定一个长度为 \(n\) 的序列 \(a_1,a_2\dots a_n\)，每个元素都是一个 \(d\) 维 \(01\) 向量，求所有不下降子序列的个数
\(1\leq n\leq 2\times 10^5\)，\(1\leq d\leq 16\)
对于 \(d\) 维向量，\(a_i\leq a_j\) 等价于 \(a_i\) 的每一维都小于等于 \(a_i\)
\(a\leq b\) 等价于 \(a|b=b\)，即 \(a\) 是 \(b\) 的子集，\(b\) 是 \(a\) 的超集
设 \(f[i]\) 表示以 \(i\) 为结尾的子序列的个数，时间复杂度 \(O(n^2)\)
考虑维护高位前缀和，设 \(s[a][b]\) 表示前 \(8\) 位是 \(a\)，后 \(8\) 位是 \(b\) 的 \(f\) 之和
查询和修改的复杂度都是 \(O(n^{\frac{d}{2}})\)
Tree chain problem
一个 \(n\) 的点的树，\(m\) 条树链，第 \(i\) 条树链的价值为 \(w_i\)。请选择一些没有公共点的树链，使得价值和最大
\(1\leq n,m\leq 10^5\)
设 \(f[x]\) 为以 \(x\) 为根的子树内选取树链的价值最大值。枚举一条以 \(x\) 为 \(\rm LCA\) 的链 \((u,v,w)\)，那么当前方案价值为 \(w\) 加上去除链上点后深度最小的点的 \(f\) 值
设 \(g[x]\) 为 \(x\) 的所有儿子的 \(f\) 之和
设链上的点为紫色，它们的儿子为绿色，那么绿色\(f\)之和 \(=\) 紫色\(g\)之和 \(-\) 紫色\(f\)之和 \(+\) \(\rm LCA\)特殊处理
问题转化为树上的树链查询与单点修改
建立 \(\rm dfs\) 序线段树 \(T\)，\(t[x]\) 存储根到 \(x\) 的和
权值的单点修改转化成 \(\rm dfs\) 序上的区间修改
树链查询首先拆成两条链减去祖先
P3577 [POI2014] TUR-Tourism
困难