石子划分问题算法设计
给定 n个石子 , 其 重 量 分 别 为 a1,a2,a3…,an, 要 求 将 其 划 分 成 m份
每一份 的 划 分 费 用 定 义 为 这 份 石 子 中 最 大 重量与最 小 重 量 的 差 的 平 方 。 总
划分费 用 等 于 m份 划 分 费 用 之 和 。
输入
第一行 两 个 正 整 数 n和 m, 接下来有 n行 每 行 一 个 正 整 数 , 表 示 一 个 石
子的重 量 ai。 (1≤n,m,ai≤1,000)
输出
将计算 出 的 最 小 总 划 分 费 用 输 出
样例输 入
4 2
4 7 1 0 1
样例输 出
18
思路:
1,先将石子重量从 小 到 大 排 序 (从 大 到 小 也 可 以 ).
2 ,假 设 f ( n , m )表 示 : n个 石 头 分 成 m 份 的 最 小 费 用 . 特 别 的 , 有