{"id":503,"date":"2017-04-24T10:57:20","date_gmt":"2017-04-24T02:57:20","guid":{"rendered":"http:\/\/kylelv.com\/?p=503"},"modified":"2018-01-18T17:05:40","modified_gmt":"2018-01-18T09:05:40","slug":"bzoj-1911-apio2010%e7%89%b9%e5%88%ab%e8%a1%8c%e5%8a%a8%e9%98%9f-%e6%96%9c%e7%8e%87%e4%bc%98%e5%8c%96","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=503","title":{"rendered":"bzoj 1911: [Apio2010]\u7279\u522b\u884c\u52a8\u961f  &#8212; \u659c\u7387\u4f18\u5316"},"content":{"rendered":"<p>&nbsp;<\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_73 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69fdef1b8fb79\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69fdef1b8fb79\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blog.kylelv.com\/?p=503\/#1911_Apio2010%E7%89%B9%E5%88%AB%E8%A1%8C%E5%8A%A8%E9%98%9F\" title=\"1911: [Apio2010]\u7279\u522b\u884c\u52a8\u961f\">1911: [Apio2010]\u7279\u522b\u884c\u52a8\u961f<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blog.kylelv.com\/?p=503\/#Description\" title=\"Description\">Description<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blog.kylelv.com\/?p=503\/#Input\" title=\"Input\">Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blog.kylelv.com\/?p=503\/#Output\" title=\"Output\">Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blog.kylelv.com\/?p=503\/#Sample_Input\" title=\"Sample Input\">Sample Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blog.kylelv.com\/?p=503\/#Sample_Output\" title=\"Sample Output\">Sample Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blog.kylelv.com\/?p=503\/#HINT\" title=\"HINT\">HINT<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blog.kylelv.com\/?p=503\/#Source\" title=\"Source\">Source<\/a><\/li><\/ul><\/nav><\/div>\n<h2 style=\"text-align: center;\"><span class=\"ez-toc-section\" id=\"1911_Apio2010%E7%89%B9%E5%88%AB%E8%A1%8C%E5%8A%A8%E9%98%9F\"><\/span>1911: [Apio2010]\u7279\u522b\u884c\u52a8\u961f<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p style=\"text-align: center;\"><span class=\"green\">Time Limit:\u00a04 Sec\u00a0\u00a0Memory Limit:\u00a064 MB<\/span><\/p>\n<h2><span class=\"ez-toc-section\" id=\"Description\"><\/span>Description<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><img decoding=\"async\" src=\"http:\/\/www.lydsy.com\/JudgeOnline\/images\/1911_1.jpg\" alt=\"\" border=\"0\" \/><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Input\"><\/span>Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><img decoding=\"async\" src=\"http:\/\/www.lydsy.com\/JudgeOnline\/images\/1911_2.jpg\" alt=\"\" border=\"0\" \/><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Output\"><\/span>Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><img decoding=\"async\" src=\"http:\/\/www.lydsy.com\/JudgeOnline\/images\/1911_3.jpg\" alt=\"\" border=\"0\" \/><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Input\"><\/span>Sample Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><span class=\"sampledata\">4<br \/>\n-1 10 -20<br \/>\n2 2 3 4<\/span><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Output\"><\/span>Sample Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><span class=\"sampledata\">9<\/span><\/div>\n<h2><span class=\"ez-toc-section\" id=\"HINT\"><\/span>HINT<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p><img decoding=\"async\" src=\"http:\/\/www.lydsy.com\/JudgeOnline\/images\/1911_4.jpg\" alt=\"\" border=\"0\" \/><\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Source\"><\/span>Source<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>dp\u65b9\u7a0b\uff1a<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/images2015.cnblogs.com\/blog\/1014417\/201704\/1014417-20170405093913316-1571676236.png\" alt=\"\" width=\"523\" height=\"37\" \/><\/p>\n<p>\u5982\u679cj&gt;k\u4e14j\u6bd4k\u66f4\u4f18<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/images2015.cnblogs.com\/blog\/1014417\/201704\/1014417-20170405093817628-504266497.png\" alt=\"\" width=\"569\" height=\"68\" \/><\/p>\n<pre class=\"lang:c++ decode:true \">#include&lt;map&gt;\r\n#include&lt;cmath&gt;\r\n#include&lt;queue&gt;\r\n#include&lt;cstdio&gt;\r\n#include&lt;cstring&gt;\r\n#include&lt;iostream&gt;\r\n#include&lt;algorithm&gt;\r\nusing namespace std;\r\n#define ll long long\r\n#define N 1000100\r\n#define db double\r\nchar xB[1&lt;&lt;15],*xS=xB,*xTT=xB;\r\n#define getc() (xS==xTT&amp;&amp;(xTT=(xS=xB)+fread(xB,1,1&lt;&lt;15,stdin),xS==xTT)?0:*xS++)\r\n#define isd(c) (c&gt;='0'&amp;&amp;c&lt;='9')\r\ninline int read(){\r\n    char xchh;\r\n    int xaa;\r\n    while(xchh=getc(),!isd(xchh));(xaa=xchh-'0');\r\n    while(xchh=getc(),isd(xchh))xaa=xaa*10+xchh-'0';return xaa;\r\n}\r\nint n,a,b,c,x[N],q[N],l,r,t;\r\nll f[N],sum[N];\r\ninline ll sqr(ll x){return x*x;}\r\ninline db cal(int j,int k){return (db)(f[j]+a*sqr(sum[j])-b*sum[j]-f[k]-a*sqr(sum[k])+b*sum[k])\/(db)(2*a*(sum[j]-sum[k]));}\r\nint main()\r\n{\r\n    scanf(\"%d%d%d%d\",&amp;n,&amp;a,&amp;b,&amp;c);\r\n    for(int i=1;i&lt;=n;i++) x[i]=read();\r\n    for(int i=1;i&lt;=n;i++) sum[i]=sum[i-1]+x[i];\r\n    for(int i=1;i&lt;=n;i++)\r\n    {\r\n        while(l&lt;r&amp;&amp;cal(q[l],q[l+1])&lt;sum[i]) l++;\r\n        t=q[l];\r\n        f[i]=f[t]+a*sqr(sum[i]-sum[t])+b*(sum[i]-sum[t])+c;\r\n        while(l&lt;r&amp;&amp;cal(q[r-1],q[r])&gt;cal(q[r],i)) r--;\r\n        q[++r]=i;\r\n    }\r\n    printf(\"%lld\\n\",f[n]);\r\n    return 0;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; 1911: [Apio2010]\u7279\u522b\u884c\u52a8\u961f Time Limit:\u00a04 Sec\u00a0\u00a0Memory  [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[5,45],"class_list":["post-503","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-dp","tag-45"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/503","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=503"}],"version-history":[{"count":2,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/503\/revisions"}],"predecessor-version":[{"id":505,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/503\/revisions\/505"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=503"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=503"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=503"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}