AquaRio 的博客

AquaRio 的博客

题解 P5336 【[THUSC2016]成绩单】

posted on 2019-11-03 11:47:31 | under 题解 |

Description

给你一个数列,每次你可以选择连续的一段删去,代价为 $a+b\times \text{(这一段最大值 - 最小值)}^2$ ,剩余部分拼到一起成为新的数列。求将原序列全部删去需要的最小总代价是多少。

Solution

肯定是区间dp啦。

我们先设 $f[i][j]$ 表示删去区间 $[i,j]$ 的最小代价。

但是这样不好转移,中间的状态非常多,并且合并的时候不知道原来状态的最大、最小值。我们在转移的时候就会很麻烦。

所以我们考虑加几个维度。

设 $g[i][j][a][b]$ 为区间 $[i,j]$ 未删除的段中,最小值为 $a$ ,最大值为 $b$ 的最小代价。

那么每次dp区间 $[i,j]$ ,最后一个位置 $j$ 的转移有两种情况:

  1. 和前面的 $[i,j-1]$ 放到一起删除,这样的话 $j$ 会影响最小值与最大值,相应的有 $g[i][j][\min(a,w[j])][\max(b,w[j])]=g[i][j-1][a][b]$ ;