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的单调递减序列的最大收益.

 

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

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

大概就是这样.

 

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

 

 

3 Trackbacks

  1. By presentation dejting exempel on 七月 12, 2019 at 3:44 下午

    presentation dejting exempel

    Codeforces 392E. Deleting Substrings – 没有回路的路

  2. By generic levitra on 七月 15, 2019 at 11:08 下午

    canada pharmacies online http://www.buylevitraa.com/

    Effectively expressed without a doubt. .

  3. By porno huis on 七月 16, 2019 at 4:53 上午

    porno huis

    Codeforces 392E. Deleting Substrings – 没有回路的路

Post a Comment

You must be logged in to post a comment.