POJ 2373 Dividing the Path DP

线段树转移的完全找不到哪里有问题,然而就是跪弃疗了。抄了份比较短的优先队列。。。。

感觉网上都是铺天盖地的单调队列,这个优先队列也真是玄学。感觉不太容易想到。

对了!这种从0开始的出题人!就应该****!=.=

f[i]表示[0,i]被刚好覆盖的最小代价。注意是刚好覆盖,别出头。

我们考虑一下,如果i位置新建一个喷射器,f[i] 必定是从 f[i – 2b] -> f[i – 2a] 这一段区间中的某一个值转移而来的。

这样子我们维护一个优先队列每次保证队列中的元素是 i – 2b -> i – 2a 这些。每次我们既不可以多加,也不能少。多加复杂度不对,少加结果可能不对。

我们预处理里,吧[a,b]这一段区间的点给搞到优先队列里。(当然刚刚说了不能多加,显然我们a+b的最小方案就是1或不可行,那么我们肯定从b+2开始转移(奇数位必定为不可行),那么我们只要加到b + 2 – a就可以了。)

然后我们转移,无非就是在优先队列里弹弹弹,发现在[i – 2b]左侧就弹弹弹。直到发现一个可行的。(当然这个是不弹的。。。说不定以后会用到)转移就行。这时候我们下一步要转移i + 2了啊。。。那么我们得吧i+2可能从i – a + 2转移的这个点加入优先队列。

最后输出就可以了。感觉好喵,,

发表评论