P5336 [THUSC2016] 成绩单 做题记录

给定一个长 nn 的序列 aa,每次操作可以选择一个区间 [l,r][l,r] 将其删去,代价为 A+B×(maxlir{ai}minlir{ai})A+B\times \left(\max\limits_{l\le i\le r}\{a_i\}-\min\limits_{l\le i\le r}\{a_i\}\right),其中 AABB 是给定的常数。

一个区间被删掉后两边的元素会自动补齐空位,求把序列删空的最小代价。

1n501\le n\le 501A15001\le A\le 15001B101\le B \le 101wi10001\le w_i\le 1000

fl,rf_{l,r} 表示把 a[l,r]a_{[l,r]} 删掉的最小代价,但是发现转移不了,因为不知道最后一次删除时序列长什么样。

那么考虑设 gl,r,x,yg_{l,r,x,y} 表示把 a[l,r]a_{[l,r]} 删至所有剩下的数都在 [x,y][x,y] 中的最小代价,则有:

fl,r=minxy{gl,r,x,y+A+B(xy)}f_{l,r}=\min\limits_{x\le y}\{g_{l,r,x,y}+A+B(x-y)\}

gg 可以通过枚举剩下的数中最靠左/靠右的来转移:

gl,r,x,y=min(minlk<r{gl,k,x,y+fk+1,r},minl<kr{fl,k1+gk,r,x,y})g_{l,r,x,y}=\min\left(\min\limits_{l\le k<r}\{g_{l,k,x,y}+f_{k+1,r}\},\min\limits_{l<k\le r}\{f_{l,k-1}+g_{k,r,x,y}\}\right)

特别的,若 a[l,r][x,y]a_{[l,r]}\in [x,y],则 gl,r,x,y=0g_{l,r,x,y}=0

那么时间复杂度 O(n3V2)O(n^3V^2),可以通过本题。