mengbierr

一个蒟蒻的博客

4月26

BZOJ4897&LOJ2292 [THUSC2016]成绩单

好强啊。
比较明显是个区间dp,但是数据范围只有50,而将状态设为f[i][j]表示删掉i-j的最小代价是不行的。
我们可以发现付出的代价和长度无关而与最大值最小值差有关,于是f[i][j][l][r]表示[i-j] 中将其中的数删到只剩下大小在[l,r]的数的最小代价。特别的,f[i][j][0][0]表示删掉[i-j]的最小代价。
转移时,首先考虑f[i][j][l][r],先贪心的将两边在[l,r]的数忽略,找到左右首个不在[l,r]内的数。然后枚举决策点k,则
f[i][j][l][r]=min(f[i][j][l][r],f[tl][k][l][r]+f[k+1][tr][l][r])
最后还要与将整个区间直接删掉的代价取最小值。(tl,tr表示处理之后的左右端点)
然后
f[i][j][0][0]=min(f[i][j][0][0],f[i][j][a][b]+A+B*(b-a)^2)
f[1][n][0][0]即为最后的答案。

发表评论

电子邮件地址不会被公开。 必填项已用*标注