P5336 [THUSC2016] 成绩单 做题记录

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

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

$1\le n\le 50$，$1\le A\le 1500$，$1\le B \le 10$，$1\le w_i\le 1000$。

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

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

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

而 $g$ 可以通过枚举剩下的数中最靠左/靠右的来转移：

$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]}\in [x,y]$，则 $g_{l,r,x,y}=0$。

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