10 9

part 13

• T1
  
  
  
  • 可以发现就是求拓扑排序的方案数
    
  • 初始答案为 \(\frac{n!}{size_x}\)
    
  • 考虑有 \(q\) 次删除操作，我们考虑维护当前还剩多少个数 \(m\)
    
  • 假如删除的数为 \(x\)，则先计算 \(size_x\) 再向上用 \(map\) 打标记，统计答案即可
    
  • 卡在的点在于不会在 \(O(\sqrt{N})\) 的时间内求解 \(n!\)
    
  
  
• P4360 斜率优化转移DP
  
  
  
  • 我们可以发现 伐木场的个数只有两个，故可以考虑直接 dp 转移
    
  • 定义 \(g_i\) 为只有一个伐木场并且建造在 \(i\) 处的 \(1-i\) 的花费总和
    
  • 假设第 \(i\) 棵树重 \(a_i\)，第 \(i\) 棵树在 \(X_i\) 的位置上
    
  • 定义 \(f_i\) 为有两个伐木场其中一个是 \(i\)，另一个 \(j < i\) 的 \(1-j\) 最小 花费总和
    
  • 我们故可以得到转移方程
    
    
    
    • \(f_i = \min(g_j + a_{j+1} \cdot (X_i - X_{j+1}) + a_{j+2} \cdot (X_i - X_{j+2})) + …… + a_{i-1} \cdot (X_i - X_{i-1}) + a_i \cdot (X_i - X_i)\)
      
    
    
  • 我们可以将式子展开
    
  • 我们记 \(suma_i = \sum_{j=1}^{i} a_j\)，\(dis_i = \sum_{j=1}^{i} a_j \cdot X_j\)
    
  • 则 \(f_i = \min(g_j + (suma_i - suma_{j}) \cdot X_i - (dis_i - dis_{j}))\)
    
  • 展开即可得到 \(suma_{j} \cdot X_i + f_i - suma_i \cdot X_i + dis_i = g_j + dis_{j}\)
    
  • 故我们可以发现 \(X_i\) 单调递增，故可以使用斜率优化转移 DP，\(O(N)\) 解决
    
  
  
• p3628 斜率优化转移DP
  
  
  
  • 定义 \(sum_i = \sum_{j=1}^{i} x_i\)
    
  • 定义 \(dp_i\) 表示给 \(1-i\) 都分配了军队后的最大战斗力之和
    
  • 则
    
    
    
    • \(dp_i = \max(dp_j + a \cdot (sum_i - sum_j)^2 + b \cdot (sum_i - sum_j) + c)\)
      
    • 即为 \(dp_i = \max(a\cdot (sum_i)^2 + b \cdot sum_i - 2 \cdot a \cdot sum_i \cdot sum_j + a \cdot (sum_j)^2 - b \cdot sum_j + c + dp_j)\)
      
    • 则有 \(2 \cdot a \cdot sum_i \cdot sum_j - c + dp_i - a\cdot (sum_i)^2 - b \cdot sum_i = a \cdot (sum_j)^2 - b \cdot sum_j + dp_j\)
      
    
    
  • 则有 \(ax + b = y\) 的形式
    
  • 考虑 \(2a\cdot sum_i\) 单调递减，\(sum_j\) 单调递增
    
  • 又由于是求取最大值故可以考虑维护上凸壳进行求解复杂度为 \(O(N)\)
    
  
  
• P1365 期望DP
  
  
  
  • 定义 \(f_i\) 为遍历到 \(i\) 的期望值
    
  • 我们考虑时刻维护 \(len\) 表示 ooo 的连续段的期望值
    
    
    
    • 若 \(i\) 为 o 则 \(f_i = f_{i - 1} + 2 \cdot len + 1\)，\(len = len + 1\)
      
    • 若 \(i\) 为 x 则 \(f_i = f_{i - 1}\)，\(len = 0\)
      
    • 若 \(i\) 为 ? 则 \(f_i = f_{i - 1} + len + 0.5\)， \(len = \frac{len+1}{2}\)
      
    
    
  
  
• P6280
  
  
  
  • 一眼就想到了是由若干环组成的，进行恰好 \(k\) 步可以等价于所有环长的最小公倍数等于 \(k\)
    
  • 然后又一眼想出，如果我们用了一些数它们的和小于 \(n\)，那么我们可以用若干个环长为 1 的环来保证它们的最小公倍数不变
    
  • 由于一些数的 lcm 为这些数每个质数的指数的 max 的乘积，故我们可以想到可以使用 \(p_1^{a_1},p_2^{a_2}……p_m^{a_m}\) 使得在和最小的情况下，lcm 最大
    
  • 故我们可以定义 \(f_{i,j}\) 表示到了第 \(i\) 个质数，前面选的环的数的总和为 \(j\) 的乘积总和
    
  • 转移枚举第 \(i\) 个质数的指数，转移即可
    
  
  
• p4161
  
  
  
  • 同上题一样只是需要求方案数
    
  
  
• p4284 概率DP
  
  
  
  • 我们考虑先算以 \(x\) 为根的子树对 \(x\) 的影响
    
  • 定义 \(f_x\) 为 \(x\) 被通电的概率
    
  • 我们令当前遍历到了子节点 \(nx\)
    
    
    
    • 令 \(w = f_{nx} \cdot p_{x,nx}\)
      
    • 那么 \(f_x = f_x + w - (f_x \cdot w)\)
      
    
    
  • 接下来我们考虑如何将父节点上的信息传递到子节点
    
  • 我们令节点 \(i\) 的答案为 \(dp_i\)
    
  • 首先根节点此时的 \(f_x\) 就是它的答案
    
  • 考虑父亲节点 \(fa\) 如何使用换根技术来计算 \(x\) 的答案
    
  • 首先 \(dp_{fa}\) 要减去 \(f_x\) 上传来的贡献
    
    
    
    • 令 \(w = f_x \cdot p_{x,fa}\) 则有 \(dp_{fa} = P_{fa} + w - (P_fa \cdot w)\)
      
    • 则 \(P_{fa} = \frac{dp_{fa}-w}{1-w}\) 须特判 \(w = 1\) 的情况
      
    • 然后按照子节点转移到父节点的方式同样的转移即可
      
    
    
  
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！