首页 > 代码库 > luogu P1725 琪露诺
luogu P1725 琪露诺
二次联通门 : luogu P1725 琪露诺
/* luogu P1725 琪露诺 DP + 线段树 用线段树维护dp[i - R] ~ dp[i - L]的最大值 然后 转移方程是 dp[i] = max (dp[i - R], dp[i - R + 1], .... dp[i - L - 1], dp[i - L]) + number[i] */ #include <cstdio> #define Max 200009 #define INF 1e7 inline int max (int a, int b) { return a > b ? a : b; } void read (int &now) { now = 0; bool flag = false; register char word = getchar (); while (word > ‘9‘ || word < ‘0‘) { if (word == ‘-‘) flag = true; word = getchar (); } while (word >= ‘0‘ && word <= ‘9‘) { now = now * 10 + word - ‘0‘; word = getchar (); } if (flag) now = -now; } int N, L, R; int number[Max]; struct Segment { struct Segment_Tree { int l; int r; int Maxn; int Mid; }; Segment_Tree tree[Max << 3]; void Build (int l, int r, int now) { tree[now].l = l; tree[now].r = r; if (l == r) return ; tree[now].Mid = (l + r) >> 1; Build (l, tree[now].Mid, now << 1); Build (tree[now].Mid + 1, r, now << 1 | 1); } int Query_Maxn (int l, int r, int now) { if (tree[now].l == l && tree[now].r == r) return tree[now].Maxn; if (r <= tree[now].Mid) return Query_Maxn (l, r, now << 1); else if (l > tree[now].Mid) return Query_Maxn (l, r, now << 1 | 1); else return max (Query_Maxn (l, tree[now].Mid, now << 1), Query_Maxn (tree[now].Mid + 1, r, now << 1 | 1)); } void Change_Single (int pos, int now, int number) { if (tree[now].l == tree[now].r) { tree[now].Maxn = number; return ; } if (pos <= tree[now].Mid) Change_Single (pos, now << 1, number); else if (pos > tree[now].Mid) Change_Single (pos, now << 1 | 1, number); tree[now].Maxn = max (tree[now << 1].Maxn, tree[now << 1 | 1].Maxn); } }; Segment Tree; int main (int argc, char *argv[]) { read (N); read (L); read (R); Tree.Build (0, N, 1); for (int i = 0; i <= N; i++) { read (number[i]); if (i <= L) Tree.Change_Single (i, 1, number[i]); } for (int i = L + 1; i <= N; i++) if (i - L >= L) Tree.Change_Single (i, 1, Tree.Query_Maxn(max(L, i - R), i - L, 1) + number[i]); else Tree.Change_Single (i, 1, number[i]); printf ("%d", Tree.Query_Maxn (N - R, N, 1)); return 0; }
luogu P1725 琪露诺
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。