首页 > 施魔法
开通博客写题解
头像 --嘤色暴撃--
发表于 2020-02-06 21:27:49
dp 第一眼看到这道题还以为是标准的划分dp，弄了好久时间复杂度还是超现在总算懂了，这题是的dp首先我们需要排序，把这些元素从小到大排好，这样确保可以直接划分(自己想一下)，并且这一段的最大值是这一段的尾，最小值是这一段的头，相当于连区间最大值最小值的线段树都不用打了用表示前个元素以为尾划分段后的最 展开全文
去ta的博客 赞 (18) 回复(0) 收起
头像 QQQQwQQQQ
发表于 2020-02-07 18:16:50
施魔法https://ac.nowcoder.com/acm/contest/3003/H 先从小到大排序，极差转换为--连续一段数尾部和开头的差值DP[i]就是前i个元素以i为尾划分段的最小值i可以是 作为前一段的新尾，DP[i]=DP[i-1]-A[i-1]+A[i]也可是新开一段k，作为段尾 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 SoloDance
发表于 2020-02-10 12:20:33
题目大意 题目链接 有n个元素（1-n）， 第i个元素能量值为ai， 可以选择至少k的元素施法， 消耗为选择的k个元素所组成的极值的差，每个元素当且仅当被用1次的最小消耗， 分析 首先排序。 f[i] 表示使用前i（包括第i）个元素的最小消耗 然后维护min(f[j - 1] - a[j]) 即 展开全文
去ta的博客 赞 (3) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”