{"id":998,"date":"2014-10-02T11:11:20","date_gmt":"2014-10-02T03:11:20","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=998"},"modified":"2014-10-02T11:27:27","modified_gmt":"2014-10-02T03:27:27","slug":"bzoj-1911-apio2010%e7%89%b9%e5%88%ab%e8%a1%8c%e5%8a%a8%e9%98%9f","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-1911-apio2010%e7%89%b9%e5%88%ab%e8%a1%8c%e5%8a%a8%e9%98%9f\/","title":{"rendered":"BZOJ 1911. [Apio2010]\u7279\u522b\u884c\u52a8\u961f"},"content":{"rendered":"<h3>Brief description: <\/h3>\n<p>\u7565\u3002\uff09<\/p>\n<h3>Analysis: <\/h3>\n<p>\u8bb0\u4ee3\u4ef7\u51fd\u6570 $$!w(x) = ax^2 + bx + c$$<\/p>\n<p>\u7136\u540e\uff1a<\/p>\n<p>$$! \\begin{aligned} f_i &#038;= \\min_{0 \\leq j < i}\\big\\{ f_j + w(s_i-s_j)\\big\\} \\\\ &#038;= \\min_{0 \\leq j < i}\\big\\{ f_j + as_j^2 - bs_j -2as_is_j\\big\\} + w(s_i) \\end{aligned}$$\n\n\u5199\u6210\u659c\u7387\u4f18\u5316\u7684\u6807\u51c6\u5f62\u5f0f\uff0cb = kx + y\n\n\u8fd9\u91cc\u6709\uff1a\n\n\n<ul>\n<li>$$k = -2as_i$$<\/li>\n<li>$$x = s_j $$<\/li>\n<li>$$y = f_j + as_j^2 &#8211; bs_j $$<\/li>\n<\/ul>\n<p>\u8fd9\u91cc $$x$$ \u548c $$k$$ \u5747\u5355\u8c03\uff08\u56e0\u4e3a $$s_i$$ \u5355\u8c03\uff09\uff0c\u5355\u8c03\u961f\u5217\u5373\u53ef\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e6) + 9;\r\nLL f&#x5B;N], s&#x5B;N], a, b, c; int q&#x5B;N], cz, op;\r\nint n;\r\n\r\nLL det(LL x1, LL y1, LL x2, LL y2){\r\n    return x1*y2 - x2*y1;\r\n}\r\n\r\n#define k (-2*a*s&#x5B;i])\r\n#define x(j) (s&#x5B;j])\r\n#define y(j) (f&#x5B;j]+a*sqr(x(j)) - b*(x(j)))\r\n#define eval(j) (k*x(j)+y(j))\r\n\r\nint dett(int p0, int p1, int p2){\r\n    LL t = det(x(p1)-x(p0), y(p1)-y(p0), x(p2)-x(p0), y(p2)-y(p0));\r\n    return t &lt; 0 ? -1 : t &gt; 0;\r\n}\r\n\r\nLL w(LL x){\r\n    return a*x*x+b*x+c;\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n); RDD(a, b, c); REP_1(i, n) s&#x5B;i] = s&#x5B;i-1] + RD();\r\n\r\n    cz = 0, op = 0; REP_1(i, n){\r\n        while (cz &lt; op &amp;&amp; eval(q&#x5B;cz]) &lt;= eval(q&#x5B;cz+1])) ++cz; f&#x5B;i] = eval(q&#x5B;cz]) + w(s&#x5B;i]);\r\n        while (cz &lt; op &amp;&amp; dett(q&#x5B;op-1], q&#x5B;op], i) &gt;= 0) --op; q&#x5B;++op] = i;\r\n    }\r\n\r\n    OT(f&#x5B;n]);\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Brief description: \u7565\u3002\uff09 Analysis: \u8bb0\u4ee3\u4ef7\u51fd\u6570 $$!w(x) = ax^2 + bx + c$$ \u7136\u540e\uff1a $$! \\begin{aligned} f_i &#038;= \\min_{0 \\leq j < i}\\big\\{ f_j + w(s_i-s_j)\\big\\} \\\\ &#038;= \\min_{0 \\leq j < i}\\big\\{ f_j + as_j^2 - bs_j -2as_is_j\\big\\} + w(s_i) \\end{aligned}$$ \u5199\u6210\u659c\u7387\u4f18\u5316\u7684\u6807\u51c6\u5f62\u5f0f\uff0cb = kx + y \u8fd9\u91cc\u6709\uff1a $$k = -2as_i$$ $$x = s_j $$ $$y [&hellip;]\n<\/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":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-998","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-g6","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/998","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=998"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/998\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=998"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=998"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=998"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}