ARC101E Ribbons on Tree
AtCoder 分析 设 $F(E)$ 表示 $E$ 中的边全部未被覆盖的方案数。 根据容斥原理可以得到 考虑怎么求 $F(E)$。可以这么考虑：把所有 $E$ 中的边去掉，那么每次选择的点对都要在同一个连通块内。假设剩下的连通块的大小为 $n_1,n_2,...,n_k$。 设 $G(n)$ 表示 $n$ 个点中两两一组的方案数。显然当 $n$ 为奇数时 $G(n)=0$，否则有 $G(...
标签 动态规划 / DP 下的文章
- 首页
- 动态规划 / DP
洛谷5279 [ZJOI2019]麻将
Luogu LOJ 分析 首先我们并不需要整副牌，我们只需要每种牌的出现次数，也就是说只需要一个长度为 $n$ 的串。 考虑怎么判一副牌能不能和。可以去做一下这道题。 我们把第一维去掉，强制 $f$ 值不超过 $4$ 、雀头数不超过 $7$ ，这样子就会有大量重复状态。爆搜可以搜出本质不同的状态只有 $2091$ 种。 那么我们把所有状态预处理出来，然后预处理出对于每个状态追加 $x\...
洛谷4244 [SHOI2008]仙人掌图
Luogu 分析 设 $f_i$ 表示 $i$ 子树中以 $i$ 为端点的最长链的长度。 如果当前边是桥，直接转移，同时更新 $ans$ 。 否则当前边在环上，先不处理。 假设我们现在在 $u$，$v$ 已经被访问过了。那么 $u$ 是这个环的底端， $v$ 是这个环的顶端。 我们把这个环找出来单独考虑。 先考虑怎么用环上的点更新答案。 要求的实际上是 $\max\{f_i+f_j+dis(...
洛谷4294 [WC2008]游览计划
Luogu 分析 斯坦纳树模板题。 设 $f_{i, S}$ 表示 $i$ 号结点，与其它节点连通性为 $S$ 时的最小代价。 转移分两种情况： 由子集转移而来 第二个方程是有后效性的，但是它长得很像三角形不等式，所以可以跑最短路转移。 代码 //It is made by M_sea #include <algorithm> #include <iostream...
APC001F XOR Tree
AtCoder 分析 考虑把边权转为点权。设每个点的点权为所有与它相连的边的边权的异或和。 那么可以发现，$u$ 到 $v$ 的路径上的边权异或 $w$，相当于 $u$ 和 $v$ 的点权异或一个 $w$。 于是问题变成给你一些数，每次可以选出两个数并让它们异或一个数，求让所有数变为 $0$ 的最小操作次数。 显然可以先贪心地去消，把所有相同的先消掉。这样子会剩下至多 $15$ 个互不相同的...
CF813D Two Melodies
Codeforces 分析 设 $f_{i, j}$ 表示第一段到了 $i$，第二段到了 $j$ 的最大长度。容易写出 $\mathcal{O}(n^3)$ 的 DP。 考虑优化。设 $maxmod_k$ 表示最大的满足 $a_j\equiv k\pmod 7$ 的 $f_{i, j}$，$maxnum_k$表示最大的满足 $a_j = k$ 的 $f_{i, j}$。于是转移变为 每次计...
CF24D Broken robot
CodeForces Luogu 分析 设 $f_{i, j}$ 表示 $(i,j)$ 到最后一排的移动步数的期望。显然有转移 对于每行，列与列之间的转移有后效性，高斯消元即可。但是这是一个 band-matrix，所以可以 $\mathcal{O}(m)$ 消元。 注意特判$m=1$的情况。 代码 #include <bits/stdc++.h> #define re reg...
洛谷2059 [JLOI2013]卡牌游戏
Luogu 分析 设 $f_{i, j}$ 表示还剩 $i$ 个人时第 $j$ 个人的获胜概率。 考虑转移。首先枚举庄家抽到的卡牌 $k$，从而得到这一轮被淘汰的人的位置 $c$。 如果 $c \neq j$，则无法转移。否则第 $c$ 个人被淘汰之后，剩下的 $i-1$ 个人要组成一个新的环，庄家为第 $c$ 个人的下一个。容易算出，当 $c > j$ 时，第 $j$ 个人是新的环里...