111017模拟 征途堆积出友情的永恒 堆优化DP

发布于 2017-10-11  12.16k 次阅读


[toggle hide="yes" title="题目" color=""]

[ttl2v]111017[/ttl2v]

【问题描述】
为了说服珍娜女王停止改造计划,Eddie 和 Hobo 踏上了去往王宫的征程。
Sunshine Empire 依次排列着(N+1)座城市,0 号城市是出发地,N 号城市是王宫。
火车是 Sunshine Empire 的主要交通工具。Eddie 和 Hobo 可以在当前的城市上车,并且在之后的某一座城市下车。从第(i-1)座城市乘坐到第 i 座城市需要花费 Ai 的费用。同时,在第 i 座城市上车需要缴纳 Bi 的税款。其中,税款属于额外支出,不属于乘坐这段火车的费用。
珍娜女王为了促进 Sunshine Empire 的繁荣发展,下令:如果连续地乘坐一段火车的费用大于这次上车前所需缴纳的税款,则这次上车前的税款可以被免除,否则免去乘坐这段火车的费用。
然而,为了保证火车的正常运行,每一次乘坐都不能连续经过超过 K 座城市(不包括上车时所在的城市),并且,Eddie 和 Hobo 的移动范围都不能超出Sunshine Empire。Eddie 想知道,到达王宫的最小总花费是多少?

【输入格式】
第一行两个整数 N,K,意义同题目描述所示。
接下来一行 N 个整数,第 i 个整数为 Ai。
接下来一行 N 个整数,第 i 个整数为 B(i-1)。

【输出格式】
一行一个整数,表示总花费的最小值。

【样例输入 1】
4 2
4 3 2 1
1 2 4 4

【样例输出 1】
11

【样例说明 1】
第一段火车经过 0,1,2 号城市,由于 4 + 3 > 1,所以税款免除,花费为 7。
第二段火车经过 2,3,4 号城市,由于 2 + 1 < 4,所以乘坐火车的费用免除,花费为 4。
总费用为 7 + 4 = 11。

【样例输入 2】
4 2
4 3 2 1
1 2 10 3

【样例输出 2】
12

【样例说明 2】
第一段火车经过 0,1 号城市,花费为 4。
第二段火车经过 1,2,3 号城市,花费为 5。
第三段火车经过 3,4 号城市,花费为 3。
总费用为 4 + 5 + 3 = 12。

【数据范围】
20%的数据满足,N≤30,K≤5。
50%的数据满足,N≤10000,K≤1000。
另有 10%的数据满足,Bi = 1。
另有 10%的数据满足,Ai = B(i-1)。
另有 10%的数据满足,N = K。
100%的数据满足,N≤500000,K≤100000,1≤Ai,Bi≤10^6。

[/toggle]

感觉这套题唯一值得总结的是第三题。

首先,裸的DP方程非常好推,为了方便起见,我们把b的下标设为[0,n-1],则有:

$$ f[i]=min(f[j]+max(s[i]-s[j],b[j])) ( i-k \leq j \leq i-1 ) $$

那么,我们如果先转化掉max的限制,那么式子可以拆成f[j]+b[j]f[j]-s[j]+s[i]两部分。

既然这道题k在一开始就是已知的,那么如果使用线段树之类的数据结构就会有些大材小用,还可能会超时,所以我们可以使用堆来维护两个式子的最小值。

开两个堆,维护两个式子(第二个式子刨去i),那么考虑取max的限制,可以知道一个可行的转移点只能在其中一个堆里出现。所以,我们先把转移点加入第一个堆,每次查找转移点先将下标不合法的弹掉,接着如果f[j]+b[j]<f[j]-s[j]+s[i],再把该点从第一个堆中弹出并加入第二个堆,可以保证第二个堆的元素一直都是合法的。接着再从第二个堆中找出最小合法转移点,两个点取min来更新当前点即可。注意,当我们取到一个合法转移点时,并不能把它删掉,因为在以后的转移中可能还需要用到。但是如果一个点在现在不合法,那么以后也不会合法,因为s[i]和下标i都是单调递增的,若在任意时刻不合法,之后也不会合法。

为什么要这么麻烦地搞这个式子?因为这样可以保证复杂度,每个点最坏会入堆、出堆各两次,时间复杂度O(nlogn)。

今天做题做得非常委屈,前两道题都想出来了正解,但是第一题最开始交的时候作差没加绝对值,一交就WA,导致心态非常崩溃。第二题写了倍增,但是第二个边界没写对只得了60,考完试人家说暴力DFS就能水过去。。。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974