代码太挫,,不忍细看…
想着想着,开始胡思乱想…
想着先按顺序砍,例如 1 2 3 4 5
如果发生变化,就会有数字跳到前面来,比如 1 3 2 4 5
这时发现 2 已无卵用,反正不需要b[2]了,干脆放最后好了
然后再变化的时候,若跳到3前面,3就是白跳了
问题就转化成 从序列中选取若干点,按顺序砍,使到n的花费最小
转移方程就是 dp[i] = min(dp[j] + B[j] * A[i]) (j < i)
然而我并不会斜率优化,顺道学了一下,随便找了一篇
版权声明:本文为博主原创文章,未经博主允许不得转载。
一旦有了意志,脚步也会轻松起来。