标签：Educational Rated Power max dp 搞懂 Smart

算法

显然为 dp

状态设计

\(dp_{i, j}\) 表示在第 \(i\) 个获得能力点的地方, 之前智慧能力值为 \(j\), 时的最大分数

状态转移

显然需要从 \(dp_{i - 1, j}\) 转移而来

枚举 \(j \in [0, i)\)
则有(注意取 \(\max\) 操作要与自己相比较)
设 第 \(i - 1\) 个能力点到第 \(i\) 个能力点中间
\(\leq k\) 的智慧检查有 \(Smart_{i - 1, k}\)
\(\leq k\) 的力量检查有 \(Power_{i - 1, k}\)
则有

\[dp_{i, j} = \max{(dp_{i - 1, j})} \]

\[dp_{i, j + 1} = \max{(dp_{i - 1, j} + Smart_{i - 1, j} + Power_{i - 1, i - j})} \]

\[dp_{i, j + 1} = \max{(dp_{i - 1, j + 1} + Smart_{i - 1, j + 1} + Power_{i - 1, i - j - 1})} \]

时间复杂度

预处理 \(Smart, Power\) 是 \(O(m^2)\)
dp 转移是 \(O(m^2)\)

代码

总结

复杂 dp 注意分类不重不漏

标签：Educational,Rated,Power,max,dp,搞懂,Smart
From： https://www.cnblogs.com/YzaCsp/p/18467445