HDU 3669 Cross the Wall

题意

 

思路

需要一定的转化的斜率优化DP。

代码

 

HDU 2829 Lawrence

题意

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

思路

依然是斜率优化DP。不过本题有两个要点必须注意:1.我们默认炸毁了某一道路之后,就不要再去管默许炸毁了的道路之前的节点了。2.一定要注意DP数组的正确初始化(因为这个我挑通宵调试了近10小时)。

详细的状态转移方程还是建议自己推导,因为下标等微妙的细节稍有相左,就会产生错误,如果确信自己的方程没有问题不妨从上面几个要点调试。如果没有掌握斜率优化DP的基本知识,请移步HDU 3507 Print Article并仔细阅读教程。

代码

 

Scroll to top