Codeforces Round #271 (Div. 2) E题 Pillars(线段树维护DP)_html/css_WEB-ITnose
程序员文章站
2022-04-07 16:17:46
...
题目地址:http://codeforces.com/contest/474/problem/E
第一次遇到这种用线段树来维护DP的题目。ASC中也遇到过,当时也很自然的想到了线段树维护DP,但是那题有简单方法,于是就没写。这次终于写出来了。。
这题的DP思想跟求最长上升子序列的思想是一样的。只不过这里的找前面最大值时会超时,所以可以用线段树来维护这个最大值,然后由于还要输出路径,所以要用线段树再来维护一个每个数在序列中所在的位置信息。
手残了好多地方,终于调试出来了。。。
代码如下:
#include#include #include #include #include #include #include #include #include
推荐阅读
-
Codeforces Round #271 (Div. 2) F题 Ant colony(线段树)_html/css_WEB-ITnose
-
Codeforces Round #271 (Div. 2) F题 Ant colony(线段树)_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) E题:Riding in a Lift(DP)_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) E题:Riding in a Lift(DP)_html/css_WEB-ITnose
-
Codeforces Round #271 (Div. 2) E题 Pillars(线段树维护DP)_html/css_WEB-ITnose
-
Codeforces Round #271 (Div. 2) E题 Pillars(线段树维护DP)_html/css_WEB-ITnose