HDU 3507 Print Article

题意

给出了一个费用计算公式,现在要你把一个数列分成若干组,每一组分别套用给出的费用计算公式计算费用。你要设计一种方法使得总费用最小。

思路

本题的DP方程推导相对容易(不过我学艺不精被卡在了这一步),之后我们会发现导出的方程完全无法满足时间限制,这个时候通过对费用公式的变形可以导出一种适用于斜率优化DP的形式。

斜率优化的操作非常复杂,幸运的是已经有人写出了详实的教程:斜率优化DP。这篇教程基本是斜率优化教程中最好理解的了,并且以这个题为例题。建议学习时手动模拟操作过程,以便形象、深入地理解。

代码

实现斜率优化的要点:1.合理正确地推导出斜率的表示形式和所有的转移方程、决策判定条件。2.正确地选择大于小于号。3.单调队列的实现,同时注意单调队列无法使用STL很好地实现,只能数组模拟。4.正确地初始化DP数组(非常重要)。

 

1 Comment

  1. HDU 2829 Lawrence | hahaschool
    September 05, 2015

    […] 本题和HDU 3507 Print Article如出一辙。都是给出了一个数列,和一个费用公式,要你设计一种把数列分为若干组之后计算出的总费用达到最小的方案。 […]

    Reply

Leave a Reply

Scroll to top