Codeforces Round #274 (Div. 2) E题:Riding in a Lift(DP)_html/css_WEB-ITnose
程序员文章站
2022-05-07 17:53:50
...
题目地址:http://codeforces.com/contest/479/problem/E
这题的动态转移方程很好想,但是最显然的是k*n*n的复杂度,明显不可以。于是就想到了用线段树来维护DP信息,但是仅仅k*n就已经濒临TLE了。。在加上个log就会TLE了,于是也不行。上网搜了一下才发现用个前缀和的小技巧就可以。= =!用了好多次了居然没有想到。。。。智商捉急。。于是剩下的就很简单了。
本来还想着,不可能走到b的另一侧,于是就只算一侧就可以了。。但是写起来才发现。。只算一侧还不如两侧一块算的代码短。。于是就一块算了。
代码如下:
#include#include #include #include #include #include #include #include #include
推荐阅读
-
Codeforces Round #277.5 (Div. 2)(C题)_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) D. Long Jumps_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) E. Riding in a Lift(DP)_html/css_WEB-ITnose
-
Codeforces Round #257 (Div. 2) A. Jzzhu and Children(简单题)_html/css_WEB-ITnose
-
Codeforces Round #248 (Div. 2) A题_html/css_WEB-ITnose
-
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 #277 (Div. 2)D(树形DP计数类)_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) C. Exams_html/css_WEB-ITnose
-
Codeforces Round #281 (Div. 2) (A、B、C、D题)_html/css_WEB-ITnose