LOJ575 「LibreOJ NOI Round #2」不等关系
LOJ 分析 假设 > 是没有限制的，那么整个序列被 < 划分为若干段。设这些段的长度为 $a_1,a_2,\cdots$，则方案数为 边界为 $dp_0=0$。将 $(-1)^{cnt_{i-1}}$ 提出后分治 NTT 即可。 代码 // =================================== // author: M_sea // website:...
标签 动态规划 / DP 下的文章
- 首页
- 动态规划 / DP
LOJ6495 「雅礼集训 2018 Day1」树
LOJ 分析 设 $dp_{i,j}$ 表示 $1\sim i$ 构成的树高度为 $j$ 的方案数。 显然树上一定存在 $(1,2)$ 这条边，因此我们转移时讨论以 $2$ 为根的子树（记做 $A$）和整棵树其它部分（记做 $B$，显然它也是一棵树）的高度关系。 转移讨论一下整棵树最深的节点在哪里即可 边界为 $dp_{1,1}=dp_{1,2}=1$。 代码 偷懒把第一问打了个表 QAq...
CF1286D LCC
Codeforces Luogu 分析 容易发现最早碰撞的一定是相邻的两个球。 我们钦定某一对球是最先撞上的以及它们的运动方向，然后考虑 DP。设 $dp_{i,0/1}$ 表示前 $i$ 个球，当前的球往左/往右，且保证最早撞上的是钦定的那一对的概率。转移讨论一下几种情况即可。 这个转移显然可以写成若干个 $2\times 2$ 的矩阵相乘。如果我们把所有方案按时间从小到大排序再枚举，则每...
CF708E Student's Camp
Codeforces Luogu 分析 显然营地不连通只能是上下分开，即存在相邻两行剩下的砖块区间没有交。 考虑 DP。设 $f_{i,j,k}$ 表示前 $i$ 行，第 $i$ 行剩下 $[j,k]$，且前 $i$ 行连通的概率。容易得到转移 于是只要求出 $d_{l-1}$ 和 $d_{l-1}sr_{i-1,l-1}$ 的前缀和即可。第一个可以提前预处理出，第二个可以在 DP 时维护...
洛谷5366 [SNOI2017]遗失的答案
Luogu LOJ 分析 首先特判掉 $G\nmid L$ 的情况。 为了方便，将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数，必须选 $X$，选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。 我们先不管那个必须选 $X$ 的条件，想一想怎么做。 注意到值域只有 $10^8$，即最多只有 $8...
洛谷5405 [CTS2019]氪金手游
Luogu LOJ 分析 首先考虑原树为外向树的情况。此时 $u$ 子树中所有点选择时间都应比 $u$ 晚。 考虑这个概率。设 $u$ 子树 $w_i$ 的和为 $s$，整棵树 $w_i$ 的和为 $S$，则 $u$ 子树中所有点选择时间都比 $u$ 晚的概率为 这个概率只和子树有关，因此可以设 $dp_{i,j}$ 表示以 $i$ 为根的子树 $w_i$ 和为 $j$ 的概率，转移即为树...
ARC096D Sweet Alchemy
AtCoder Luogu 分析 考虑差分，则问题变为每次选择一棵子树，消耗 $\sum m_i$ 的材料，造出 $sz$ 个物品，且每棵不是原树的子树都只能选至多 $D$ 次。 令每棵子树的 $m_i$ 之和为其代价，$sz$ 为其收益，则相当于一个多重背包。 然而 $D$ 在 $10^9$ 级别，直接多重背包显然无法通过。 考虑一个错误的贪心：设 $w_i$ 为收益，$v_i$ 为代价，...
CF724E Goods transportation
Codeforces Luogu 分析 容易想到一个网络流做法，即源点向每个点连容量为 $p_i$ 的边，每个点向汇点连容量为 $s_i$ 的边，每个点向编号比它大的点连容量为 $c$ 的边，然后求最大流即可。 发现最大流不好求，而图比较特殊，可以考虑 DP 求最小割。 设 $dp_{i,j}$ 表示前 $i$ 个点有 $j$ 个点和源点相连的最小割。转移这样考虑：如果 $i$ 与源点相连，...
CF568E Longest Increasing Subsequence
Codeforces Luogu 分析 考虑普通 LIS 问题的解法，即设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值，转移时二分即可。 考虑沿用到这道题中。设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值，$g_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值所在位置；再设 $l_i$ 表示以 $i$ 结尾的 LIS 长度，$p_i$ 表示以 $i$ 结尾...
AGC030D Inversion Sum
AtCoder Luogu 分析 设 $dp_{x,y}$ 表示 $a_x > a_y$ 的概率（假设每个操作发生的概率都为 $\frac{1}{2}$）。 对于每个操作 $(i,j)$，我们会让所有的 $dp_{i,k}$ 和 $dp_{j,k}$ 都变为 $\frac{1}{2}(dp_{i,k}+dp_{j,k})$，会让所有的 $dp_{k,i}$ 和 $dp_{k,j}$ 都...