LOJ575 「LibreOJ NOI Round #2」不等关系
LOJ分析假设 > 是没有限制的，那么整个序列被 < 划分为若干段。设这些段的长度为 $a_1,a_2,\cdots$，则方案数为边界为 $dp_0=0$。将 $(-1)^{cnt_{i-1}}$ 提出后分治 NTT 即可。代码// =================================== // author: M_sea // website: https...
标签 动态规划 下的文章
- 首页
- 动态规划
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
CodeforcesLuogu分析容易发现最早碰撞的一定是相邻的两个球。我们钦定某一对球是最先撞上的以及它们的运动方向，然后考虑 DP。设 $dp_{i,0/1}$ 表示前 $i$ 个球，当前的球往左/往右，且保证最早撞上的是钦定的那一对的概率。转移讨论一下几种情况即可。这个转移显然可以写成若干个 $2\times 2$ 的矩阵相乘。如果我们把所有方案按时间从小到大排序再枚举，则每次相当于修...
CF708E Student's Camp
CodeforcesLuogu分析显然营地不连通只能是上下分开，即存在相邻两行剩下的砖块区间没有交。考虑 DP。设 $f_{i,j,k}$ 表示前 $i$ 行，第 $i$ 行剩下 $[j,k]$，且前 $i$ 行连通的概率。容易得到转移于是只要求出 $d_{l-1}$ 和 $d_{l-1}sr_{i-1,l-1}$ 的前缀和即可。第一个可以提前预处理出，第二个可以在 DP 时维护。边界为 $...
洛谷4007 小 Y 和恐怖的奴隶主
LuoguLOJ分析看到数据范围容易想到矩阵快速幂，因此可以考虑 DP。设 $dp_{i,a,b,c}$ 表示前 $i$ 次攻击，场上有 $a$ 个一血、$b$ 个二血、$c$ 个三血的概率。转移稍微讨论一下即可。为了求答案，再设一个 $f_i$ 表示前 $i$ 次攻击对 Boss 的期望伤害，从所有 $dp_{i,a,b,c}$ 由 $\frac{1}{a+b+c+1}$ 的概率转移过来。...
洛谷5366 [SNOI2017]遗失的答案
LuoguLOJ分析首先特判掉 $G\nmid L$ 的情况。为了方便，将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数，必须选 $X$，选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。我们先不管那个必须选 $X$ 的条件，想一想怎么做。注意到值域只有 $10^8$，即最多只有 $8$ 个质因子...
LOJ2695 「POI2012」衣帽间 Cloakroom
LOJ分析考虑将所有询问离线并按左端点从小到大排序。则 $a_i\leq m$ 的限制我们可以通过将物品按左端点排序并依次加入来解决。考虑 DP。设 $dp_i$ 表示物品权值之和为 $i$ 时右端点最远能到哪。这样子对于每个询问我们只需要查询 $dp_k$ 是否大于 $m+s$ 即可。转移类似于 0/1 背包。代码// ===================================...
洛谷5405 [CTS2019]氪金手游
LuoguLOJ分析首先考虑原树为外向树的情况。此时 $u$ 子树中所有点选择时间都应比 $u$ 晚。考虑这个概率。设 $u$ 子树 $w_i$ 的和为 $s$，整棵树 $w_i$ 的和为 $S$，则 $u$ 子树中所有点选择时间都比 $u$ 晚的概率为这个概率只和子树有关，因此可以设 $dp_{i,j}$ 表示以 $i$ 为根的子树 $w_i$ 和为 $j$ 的概率，转移即为树形背包。现在...
ARC096D Sweet Alchemy
AtCoderLuogu分析考虑差分，则问题变为每次选择一棵子树，消耗 $\sum m_i$ 的材料，造出 $sz$ 个物品，且每棵不是原树的子树都只能选至多 $D$ 次。令每棵子树的 $m_i$ 之和为其代价，$sz$ 为其收益，则相当于一个多重背包。然而 $D$ 在 $10^9$ 级别，直接多重背包显然无法通过。考虑一个错误的贪心：设 $w_i$ 为收益，$v_i$ 为代价，按 $\fr...
LOJ3271 「JOISC 2020 Day1」建筑装饰 4
LOJ分析设 $dp_{i,0/1,0/1}$ 表示前 $i$ 位，第 $i$ 位选 A / B 时所有满足条件的方案中最多能有多少个 A / B。转移分四种情况（$a_{i-1}\leq a_i$、$a_{i-1}\leq b_i$、$b_{i-1}\leq a_i$、$b_{i-1}\leq b_i$）即可。考虑从后往前构造方案。设 $sa$ 表示已选的 A 的数量，$sb$ 表示已选的...