标签: 动态规划

4 篇文章

义乌中学暑假集训 2021.07.15 C
白云有一颗 $n$ 个节点的树,每个点有一个点权 白兔需要找到两条点不相交的路径,要求最大化这两条路径覆盖点的点权和 $n\leq 10^5$。 Sol 换根 DP。 考虑两条路径的形态。 从两个子树中各抽出一条链。在一棵子树中抽一条经过根的链,再在剩余的儿子的子树中抽一条链。在一棵子树中抽一条子树内的链,再在经过这个子树的父亲抽一条链。 然后维护…
义乌中学暑假集训 2021.07.13 C
给定一棵 $n$ 个节点的带权有根树,保证每个节点权值均为非负整数。 定义 $f(x)$​,表示对于节点 $x$​,包含 $x$​ 的节点的平均值最大的连通块内平均值。 求 $\min_{i=1}^n f(i)$。 $n\leq 10^5$。 Sol 既有最小也有最大,想到二分。 可以二分答案,每次 check 的时候数字权值减去 mid,跑一次换…
义乌中学暑假集训 2021.07.13 B
给定串 $s$,问其中有多少 namomo 子序列。定义一个子序列 $t$​ 是 namomo 子序列,当且仅当: $t_3=t_5$$t_4=t_6$$t_1,t_2,t_3,t_4$​ 两两不同。 输出答案 $\bmod 998244353$ 的结果。 $6\leq |s|\leq 10^6$。 Sol 这题有多种做法,这里提供一种比较简洁小清…
P2523 [HAOI2011]Problem c
Link 题目链接:P2523 Solution 设 $f[i][j]$ 表示剩余 $n - m$人中编号 $\ge i$ 的人,其中 $j$ 个人的编号已经确定的方案数 $$f[i][j] = \sum \limits_{k = 0}^j f[i + 1][j - k] \times C_j^k (0 \le j \le n - s[i] - i…