给定一个长 n 的序列 a,每次操作可以选择一个区间 [l,r] 将其删去,代价为 A+B×(l≤i≤rmax{ai}−l≤i≤rmin{ai}),其中 A 和 B 是给定的常数。
一个区间被删掉后两边的元素会自动补齐空位,求把序列删空的最小代价。
1≤n≤50,1≤A≤1500,1≤B≤10,1≤wi≤1000。
设 fl,r 表示把 a[l,r] 删掉的最小代价,但是发现转移不了,因为不知道最后一次删除时序列长什么样。
那么考虑设 gl,r,x,y 表示把 a[l,r] 删至所有剩下的数都在 [x,y] 中的最小代价,则有:
fl,r=x≤ymin{gl,r,x,y+A+B(x−y)}
而 g 可以通过枚举剩下的数中最靠左/靠右的来转移:
gl,r,x,y=min(l≤k<rmin{gl,k,x,y+fk+1,r},l<k≤rmin{fl,k−1+gk,r,x,y})
特别的,若 a[l,r]∈[x,y],则 gl,r,x,y=0。
那么时间复杂度 O(n3V2),可以通过本题。