web analytics

Codeforces 392E. Deleting Substrings

题目连接:http://codeforces.com/problemset/problem/392/E

分析:

区间DP.

根据题目我们发现如果我们光维护一个 从i到j取完的值.

因为这道题有单调递增和单调递减的部分.所以我们可以单独来维护这几个部分.然后组合即可>

 

所以我们设:

F[i][j] 表示 区间[i,j]删完的最大收益

g[i][j]表示把区间[i,j] 删成公差为1的单调递增序列的最大收益

h[i][j]表示把区间[i,j]删成公差为1的单调递减序列的最大收益.

 

我们需要枚举区间的长度.和枚举左七点.

维护上升序列. --> 维护递减序列 --> 维护区间断点 -->组合

大概就是这样.

 

具体转移代码可能会比较好明白:

 

 

Post a Comment

You must be logged in to post a comment.