Codeforces 189 C. Kalila and Dimna in the Logging Industry

代码太挫,,不忍细看…

想着想着,开始胡思乱想…

想着先按顺序砍,例如 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)

然而我并不会斜率优化,顺道学了一下,随便找了一篇

版权声明:本文为博主原创文章,未经博主允许不得转载。

一旦有了意志,脚步也会轻松起来。

Codeforces 189 C. Kalila and Dimna in the Logging Industry

相关文章:

你感兴趣的文章:

标签云: