将一个序列调整为单调序列的最小代价问题

来源：百度知道 编辑：UC知道 时间：2024/06/07 16:36:36
给出一个长度最多达到3000的整数序列，我们可以改变这个序列的任意一个元素的值。对于这些改变，我们记下每次改变的代价，即改变后的元素值与改变前的元素值的差值的绝对值。每次改变的代价的总和就是调整的总代价。要求在代价最小的情况下，将序列调整成为一个单调的序列（单调性可以不严格，并且单调递增和单调递减均可）。那么，应该使用怎样的算法？
我觉得这是数学的内容啊...

个人觉得可以用取中值的办法：

代价最小，那就是要尽量顺着原序列。
平均分两部分，比较前后1500个数的均数，如果前面的比较大，那就调成递减，否则相反；
平均分四部分，以各自的均值为基准，再比较前后750个的均值。

依此类推。

回溯 贪心 动态规划
没有时限你还可以 递归模拟。。。

我觉得这是数学的内容啊...
题目最后都问你 应该使用怎样的算法了 肯定是计算机算法题 就是用回溯 贪心法 和动态规划
虽说数学与计算机有密切关系，但数学指提供个大致思路，配合计算机强大的计算功能模拟和典型的计算机算法，能很好的解决问题。

问错地方了吧，应该到电脑区去问。

具体问题回答.