Codeforces 392E Deleting Substrings

Posted by

[TOC]

题目链接

http://codeforces.com/problemset/problem/392/E

题意

给定一个数列,每次从中删去一个子序列$ w_l,w_{l+1},\ldots,w_r $,子序列的数值满足公差为$ 1$且成一个山峰的形状(单调递增、单调递减或先单调递增再单调递减),每删去一个子序列可以获得$ v_{r-l+1} $的收益,问进行多次删除操作的最大收益。

题解

首先对于一个子序列$ w_l,w_{l+1},\ldots,w_r $,设其中最大值为$ w_i $,我们删除这个序列获得的最大收益应为$ v_{(i-1-l+1)+(i-r+1)}=v_{2i-l-r+1} $。
区间DP:设$ f[i][j] $表示把区间$ [i,j] $删完的最大收益,$ g[i][j] $表示把区间$ [i,j] $删成公差为$ 1$的单调递增序列的最大收益,$ h[i][j] $表示把区间$ [i,j] $删成公差为$latex 1$的单调递减序列的最大收益。
状态转移方程:
$$ f[i][j]=max\{g[i][k]+h[k][j]+v[2\cdot w[k]-w[i]-w[j]+1]\},\quad i\leq k\leq j $$
边界条件:当$ i=j $时$ f[i][j]=v[1],g[i][j]=h[i][j]=0 $。

代码

Leave a Reply

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