Codeforces 392E Deleting Substrings

Posted by

题目链接

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] \)删成公差为\(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

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