{"id":140,"date":"2010-08-02T08:42:17","date_gmt":"2010-08-02T00:42:17","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=140"},"modified":"2012-03-03T08:42:31","modified_gmt":"2012-03-03T00:42:31","slug":"hoj-2491-sequences","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/hoj-2491-sequences\/","title":{"rendered":"HOJ 2491. Sequences"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u5c06\u6570\u5217 {an} \u5212\u5206\u6210\u4e00\u4e9b\u957f\u5ea6\u5728 [l, r] \u4e4b\u95f4\u7684\u5b50\u6bb5\uff0c\u6bcf\u4e2a\u5b50\u6bb5\u7684\u5f97\u5206\u7b49\u4e8e\u9996\u5c3e\u9879\u7684\u548c\u3002\uff08\u6ce8\u610f\u662f\u5b8c\u7f8e\u5212\u5206\uff0c\u4e0d\u8981\u7559\u7a7a\u9699\u3002~\uff09<\/p>\n<h3>Note :<\/h3>\n<p>\u5355\u8c03\u961f\u5217\u7ec3\u4e60\u9898\u3002\u3002<br \/>\ndp[i] = max{dp[j] + a[j+1]} + a[i]   |  j \u8981\u6ee1\u8db3\u6761\u4ef6<br \/>\n\u628a dp[i] \u548c a[i+1] \u5b58\u5728\u4e00\u8d77\u7b80\u5316\u7ef4\u62a4\u3002\u3002<\/p>\n<pre lang=\"cpp\">\r\n#include <iostream>\r\nusing namespace std;\r\nconst int INF = 0x7fffffff;\r\nconst int N = 500002;\r\n\r\nint a[N], d[N], q[N], cz, op;\r\nint n, l, r;\r\n\r\nvoid push(int x){\r\n    while (cz <= op &#038;&#038; d[x] >= d[q[op]])\r\n        op--;\r\n    q[++op] = x;\r\n}\r\n\r\nvoid init(){\r\n    scanf(\"%d%d\", &l, &r);\r\n    for (int i=1;i<=n;i++) scanf(\"%d\", &#038;a[i]);\r\n    a[n+1] = 0;\r\n}\r\n\r\nvoid solve(){\r\n    d[0] = a[1]; cz = 0, op = -1;\r\n\r\n    for (int i=1;i<l;++i) d[i] = -INF;\r\n    \r\n    for (int i=l;i<=n;++i){\r\n        push(i - l); if (q[cz] < i - r) ++cz;\r\n        d[i] = d[q[cz]] + a[i] + a[i+1];\r\n    }\r\n}\r\n\r\nint main(){\r\n    while (cin >> n){\r\n        init(); solve();\r\n        cout << d[n] << endl;\r\n    }\r\n}\r\n<\/pre>\n<h3>External link :<\/h3>\n<p><a href=\" http:\/\/acm.hit.edu.cn\/judge\/show.php?Proid=2941\"><br \/>\nhttp:\/\/acm.hit.edu.cn\/judge\/show.php?Proid=2941<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u5c06\u6570\u5217 {an} \u5212\u5206\u6210\u4e00\u4e9b\u957f\u5ea6\u5728 [l, r] \u4e4b\u95f4\u7684\u5b50\u6bb5\uff0c\u6bcf\u4e2a\u5b50\u6bb5\u7684\u5f97\u5206\u7b49\u4e8e\u9996\u5c3e\u9879\u7684\u548c\u3002\uff08\u6ce8\u610f\u662f\u5b8c\u7f8e\u5212\u5206\uff0c\u4e0d\u8981\u7559\u7a7a\u9699\u3002~\uff09 Note : \u5355\u8c03\u961f\u5217\u7ec3\u4e60\u9898\u3002\u3002 dp[i] = max{dp[j] + a[j+1]} + a[i] | j \u8981\u6ee1\u8db3\u6761\u4ef6 \u628a dp[i] \u548c a[i+1] \u5b58\u5728\u4e00\u8d77\u7b80\u5316\u7ef4\u62a4\u3002\u3002 #include using namespace std; const int INF = 0x7fffffff; const int N = 500002; int a[N], d[N], q[N], cz, op; int n, l, r; void push(int x){ while [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-140","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-2g","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/140","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=140"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/140\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=140"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=140"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=140"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}