2022年4月10日 6次阅读 来源: hestyle
我们将给定的数组 A 分成 K 个相邻的非空子数组 ,我们的分数由每个子数组内的平均值的总和构成.计算我们所能得到的最大分数是多少.
注意我们必须使用 A 数组中的每一个数进行分组,并且分数不一定需要是整数.
答案误差在 10^-6 内被视为是正确的.
思 路 分 析 : \color{blue}思路分析: 思路分析:对于这道题,刚开始我想着利用贪心策略来处理,蛋试发现问题远没有贪心策略那么简单.蛋试一般这种数组分割求最大值都是用贪心策略,动态规划,所以转移到动态规划.
本题同样采用这种策略快速计算数组段的和.使用sum[i]记录数组A的前i个元素的和,所以数组段[j i)的和 = sum[i] - sum[j]
接着就是动态数组以及状态转移方程的构建.
dp[i][k]用于记录A数组前i个元素分成k段平均值和的最大值.
原文作者:hestyle