{"id":169,"date":"2010-03-20T14:36:00","date_gmt":"2010-03-20T06:36:00","guid":{"rendered":"http:\/\/localhost\/?p=169"},"modified":"2010-03-20T14:36:00","modified_gmt":"2010-03-20T06:36:00","slug":"hnoi2008_toy_packing_toy","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=169","title":{"rendered":"[HNOI2008]\u73a9\u5177\u88c5\u7bb1toy"},"content":{"rendered":"\n<p>[HNOI2008]\u73a9\u5177\u88c5\u7bb1toy<\/p>\n<p>Time Limit:1000MS&#160; Memory Limit:165536K<br \/>Total Submit:204 Accepted:76<\/p>\n<p><strong>Description <\/strong><\/p>\n<p> P\u6559\u6388\u8981\u53bb\u770b\u5965\u8fd0\uff0c\u4f46\u662f\u4ed6\u820d\u4e0d\u4e0b\u4ed6\u7684\u73a9\u5177\uff0c\u4e8e\u662f\u4ed6\u51b3\u5b9a\u628a\u6240\u6709\u7684\u73a9\u5177\u8fd0\u5230\u5317\u4eac\u3002\u4ed6\u4f7f\u7528\u81ea\u5df1\u7684\u538b\u7f29\u5668\u8fdb\u884c\u538b\u7f29\uff0c\u5176\u53ef\u4ee5\u5c06\u4efb\u610f\u7269\u54c1\u53d8\u6210\u4e00\u5806\uff0c\u518d\u653e\u5230\u4e00\u79cd\u7279\u6b8a\u7684\u4e00 \u7ef4\u5bb9\u5668\u4e2d\u3002P\u6559\u6388\u6709\u7f16\u53f7\u4e3a1&#8230;N\u7684N\u4ef6\u73a9\u5177\uff0c\u7b2ci\u4ef6\u73a9\u5177\u7ecf\u8fc7\u538b\u7f29\u540e\u53d8\u6210\u4e00\u7ef4\u957f\u5ea6\u4e3aCi.\u4e3a\u4e86\u65b9\u4fbf\u6574\u7406\uff0cP\u6559\u6388\u8981\u6c42\u5728\u4e00\u4e2a\u4e00\u7ef4\u5bb9\u5668\u4e2d\u7684\u73a9\u5177\u7f16\u53f7\u662f\u8fde\u7eed \u7684\u3002\u540c\u65f6\u5982\u679c\u4e00\u4e2a\u4e00\u7ef4\u5bb9\u5668\u4e2d\u6709\u591a\u4e2a\u73a9\u5177\uff0c\u90a3\u4e48\u4e24\u4ef6\u73a9\u5177\u4e4b\u95f4\u8981\u52a0\u5165\u4e00\u4e2a\u5355\u4f4d\u957f\u5ea6\u7684\u586b\u5145\u7269\uff0c\u5f62\u5f0f\u5730\u8bf4\u5982\u679c\u5c06\u7b2ci\u4ef6\u73a9\u5177\u5230\u7b2cj\u4e2a\u73a9\u5177\u653e\u5230\u4e00\u4e2a\u5bb9\u5668\u4e2d\uff0c\u90a3\u4e48\u5bb9\u5668\u7684 \u957f\u5ea6\u5c06\u4e3a <br \/>x=j-i+Sigma(Ck) i&lt;=K&lt;=j <br \/>\u5236\u4f5c\u5bb9\u5668\u7684\u8d39\u7528\u4e0e\u5bb9\u5668\u7684\u957f\u5ea6\u6709\u5173\uff0c\u6839\u636e\u6559\u6388\u7814\u7a76\uff0c\u5982\u679c\u5bb9\u5668\u957f\u5ea6\u4e3ax,\u5176\u5236\u4f5c\u8d39\u7528\u4e3a(X-L)^2.\u5176\u4e2dL\u662f\u4e00\u4e2a <br \/>\u5e38\u91cf\u3002P\u6559\u6388\u4e0d\u5173\u5fc3\u5bb9\u5668\u7684\u6570\u76ee\uff0c\u4ed6\u53ef\u4ee5\u5236\u4f5c\u51fa\u4efb\u610f\u957f\u5ea6\u7684\u5bb9\u5668\uff0c\u751a\u81f3\u8d85\u8fc7L\u3002\u4f46\u4ed6\u5e0c\u671b\u8d39\u7528\u6700\u5c0f. <\/p>\n<p><strong>Input <\/strong><\/p>\n<p> \u7b2c\u4e00\u884c\u8f93\u5165\u4e24\u4e2a\u6574\u6570N\uff0cL.\u63a5\u4e0b\u6765N\u884c\u8f93\u5165Ci.1&lt;=N&lt;=50000,1&lt;=L,Ci&lt;=10^7 <\/p>\n<p><strong>Output <\/strong><\/p>\n<p> \u8f93\u51fa\u6700\u5c0f\u8d39\u7528 <\/p>\n<p><strong>Sample Input <\/strong><\/p>\n<p>5 4<br \/>3<br \/>4<br \/>2<br \/>1<br \/>4<\/p>\n<p><strong>Sample Output <\/strong><\/p>\n<p>1<\/p>\n<p><strong>Source <\/strong><\/p>\n<p>\u989d\u3002\u3002\u770b\u4e86\u51b3\u7b56\u5355\u8c03\u6027\u4e4b\u540e\u51b3\u5b9aA\u4e2a\u4e00\u9898\uff0c\u7ed3\u679c\u641e\u4e86\u534a\u5929\uff0c\u6211\u592a\u83dc\u4e86555\u3002\u3002\u3002<br \/>\u8fd9\u662f\u5f88\u57fa\u672c\u7684\u51b3\u7b56\u5355\u8c03\u6027\uff0c\u4e5f\u53ef\u4ee5\u7528\u659c\u7387\u4f18\u5316\u6765\u641e\uff0c\u4e0d\u8fc7\u5355\u8c03\u6027\u611f\u89c9\u6bd4\u8f83\u76f4\u89c2\uff0c\u800c\u4e14\u4e5f\u80fdAC(*^__^*) <br \/>\u5c31\u662f\u7528\u4e00\u4e2a\u53cc\u7aef\u961f\u5217\u6765\u4fdd\u5b58\u5f53\u524d\u7684\u51b3\u7b56\u533a\u95f4\uff0c\u7528\u4e8c\u5206\u67e5\u627e\u5bfb\u5206\u754c\u70b9\u3002\u3002<br \/>Code\uff1a<br \/>#include&lt;cstdio&gt;<br \/>#include&lt;iostream&gt;<br \/>#include&lt;algorithm&gt;<br \/>#include&lt;string&gt;<br \/>#include&lt;vector&gt;<br \/>#include&lt;cstring&gt;<br \/>#include&lt;deque&gt;<br \/>#define rep(i,n) for(int i=0;i&lt;n;i++)<br \/>#define pb push_back<br \/>using namespace std;<br \/>const int inf=~0U&gt;&gt;1;<br \/>const int maxn=50000+1;<br \/>typedef long long ll;<br \/>struct node<br \/>{<br \/>    int l,r,ch;<br \/>    node(){}<br \/>    node(int _l,int _r,int _ch):l(_l),r(_r),ch(_ch){}<br \/>};<br \/>ll Sum[maxn]={0},Dp[maxn];<br \/>int top=0;<br \/>int L,n;<br \/>ll Cost(int l,int r)<br \/>{<br \/>    ll x=Sum[r]-Sum[l-1]+r-l;<br \/>    x-=L;<br \/>    return x*x;<br \/>}<br \/>ll Get(int New,int Old)<br \/>{<br \/>    if(Old&gt;=New)return inf;<br \/>    return Dp[Old]+Cost(Old+1,New);<br \/>}<br \/>int binary(node t,int i)<br \/>{<br \/>    int l=t.l,r=t.r;<br \/>    #define check(m) (Get(m,t.ch)&lt;Get(m,i))<br \/>    if(check(r)) return r;<br \/>    while(l+1&lt;r)<br \/>    {<br \/>        int m=(l+r)\/2;<br \/>        if(check(m)) l=m;<br \/>        else r=m;<br \/>    }<br \/>    return l;<br \/>    #undef check<br \/>}<br \/>void Init()<br \/>{<br \/>    scanf(&quot;%d %d&quot;,&amp;n,&amp;L);<br \/>    rep(i,n)scanf(&quot;%lld&quot;,Sum+i+1);<br \/>    for(int i=1;i&lt;=n;i++) Sum[i]+=Sum[i-1];<br \/>}<br \/>void Work()<br \/>{<br \/>    Dp[0]=0;deque&lt;node&gt; D;<br \/>    D.pb(node(1,n,0));<br \/>    for(int i=1;i&lt;=n;i++)<br \/>    {<br \/>        Dp[i]=Get(i,D.front().ch);<br \/>        if(D.front().l&lt;D.front().r)<br \/>            D.front().l++;<br \/>        else<br \/>            D.pop_front();<br \/>        node t;int e;<br \/>        while(D.size())<br \/>        {<br \/>            t=D.back();<br \/>            if(Get(t.l,i)&lt;=Get(t.l,t.ch))<br \/>            {<br \/>                D.pop_back();<br \/>            }<br \/>            else<br \/>            {<br \/>                e=binary(t,i);<br \/>                D.back().r=e;<br \/>                break;<br \/>            }<br \/>        }<br \/>        if(D.size()==0)<br \/>            D.pb(node(i+1,n,i));<br \/>        else if(e&lt;n) D.pb(node(e+1,n,i));<br \/>    }<br \/>    cout&lt;&lt;Dp[n]&lt;&lt;endl;<br \/>}<br \/>int main()<br \/>{<br \/>    \/\/freopen(&quot;in&quot;,&quot;r&quot;,stdin);<br \/>    Init();<br \/>    Work();<br \/>} <\/p>\n","protected":false},"excerpt":{"rendered":"<p>[HNOI2008]\u73a9\u5177\u88c5\u7bb1toy Time Limit:1000MS&#160; Memory Limit:165536KTotal Submit:204 Accepted:76 Description P\u6559\u6388\u8981\u53bb\u770b\u5965\u8fd0\uff0c\u4f46\u662f\u4ed6\u820d\u4e0d\u4e0b\u4ed6\u7684\u73a9\u5177\uff0c\u4e8e\u662f\u4ed6\u51b3\u5b9a\u628a\u6240\u6709\u7684\u73a9\u5177\u8fd0\u5230\u5317\u4eac\u3002\u4ed6\u4f7f\u7528\u81ea\u5df1\u7684\u538b\u7f29\u5668\u8fdb\u884c\u538b\u7f29\uff0c\u5176\u53ef\u4ee5\u5c06\u4efb\u610f\u7269\u54c1\u53d8\u6210\u4e00\u5806\uff0c\u518d\u653e\u5230\u4e00\u79cd\u7279\u6b8a\u7684\u4e00 \u7ef4\u5bb9\u5668\u4e2d\u3002P\u6559\u6388\u6709\u7f16\u53f7\u4e3a1&#8230;N\u7684N\u4ef6\u73a9\u5177\uff0c\u7b2ci\u4ef6\u73a9\u5177\u7ecf\u8fc7\u538b\u7f29\u540e\u53d8\u6210\u4e00\u7ef4\u957f\u5ea6\u4e3aCi.\u4e3a\u4e86\u65b9\u4fbf\u6574\u7406\uff0cP\u6559\u6388\u8981\u6c42\u5728\u4e00\u4e2a\u4e00\u7ef4\u5bb9\u5668\u4e2d\u7684\u73a9\u5177\u7f16\u53f7\u662f\u8fde\u7eed \u7684\u3002\u540c\u65f6\u5982\u679c\u4e00\u4e2a\u4e00\u7ef4\u5bb9\u5668\u4e2d\u6709\u591a\u4e2a\u73a9\u5177\uff0c\u90a3\u4e48\u4e24\u4ef6\u73a9\u5177\u4e4b\u95f4\u8981\u52a0\u5165\u4e00\u4e2a\u5355\u4f4d\u957f\u5ea6\u7684\u586b\u5145\u7269\uff0c\u5f62\u5f0f\u5730\u8bf4\u5982\u679c\u5c06\u7b2ci\u4ef6\u73a9\u5177\u5230\u7b2cj\u4e2a\u73a9\u5177\u653e\u5230\u4e00\u4e2a\u5bb9\u5668\u4e2d\uff0c\u90a3\u4e48\u5bb9\u5668\u7684 \u957f\u5ea6\u5c06\u4e3a x=j-i+Sigma(Ck) i&lt;=K&lt;=j \u5236\u4f5c\u5bb9\u5668\u7684\u8d39\u7528\u4e0e\u5bb9\u5668\u7684\u957f\u5ea6\u6709\u5173\uff0c\u6839\u636e\u6559\u6388\u7814\u7a76\uff0c\u5982\u679c\u5bb9\u5668\u957f\u5ea6\u4e3ax,\u5176\u5236\u4f5c\u8d39\u7528\u4e3a(X-L)^2.\u5176\u4e2dL\u662f\u4e00\u4e2a \u5e38\u91cf\u3002P\u6559\u6388\u4e0d\u5173\u5fc3\u5bb9\u5668\u7684\u6570\u76ee\uff0c\u4ed6\u53ef\u4ee5\u5236\u4f5c\u51fa\u4efb\u610f\u957f\u5ea6\u7684\u5bb9\u5668\uff0c\u751a\u81f3\u8d85\u8fc7L\u3002\u4f46\u4ed6\u5e0c\u671b\u8d39\u7528\u6700\u5c0f. Input \u7b2c\u4e00\u884c\u8f93\u5165\u4e24\u4e2a\u6574\u6570N\uff0cL.\u63a5\u4e0b\u6765N\u884c\u8f93\u5165Ci.1&lt;=N&lt;=50000,1&lt;=L,Ci&lt;=10^7 Output \u8f93\u51fa\u6700\u5c0f\u8d39\u7528 Sample Input 5 434214 Sample Output 1 Source \u989d\u3002\u3002\u770b\u4e86\u51b3\u7b56\u5355\u8c03\u6027\u4e4b\u540e\u51b3\u5b9aA\u4e2a\u4e00\u9898\uff0c\u7ed3\u679c\u641e\u4e86\u534a\u5929\uff0c\u6211\u592a\u83dc\u4e86555\u3002\u3002\u3002\u8fd9\u662f\u5f88\u57fa\u672c\u7684\u51b3\u7b56\u5355\u8c03\u6027\uff0c\u4e5f\u53ef\u4ee5\u7528\u659c\u7387\u4f18\u5316\u6765\u641e\uff0c\u4e0d\u8fc7\u5355\u8c03\u6027\u611f\u89c9\u6bd4\u8f83\u76f4\u89c2\uff0c\u800c\u4e14\u4e5f\u80fdAC(*^__^*) \u5c31\u662f\u7528\u4e00\u4e2a\u53cc\u7aef\u961f\u5217\u6765\u4fdd\u5b58\u5f53\u524d\u7684\u51b3\u7b56\u533a\u95f4\uff0c\u7528\u4e8c\u5206\u67e5\u627e\u5bfb\u5206\u754c\u70b9\u3002\u3002Code\uff1a#include&lt;cstdio&gt;#include&lt;iostream&gt;#include&lt;algorithm&gt;#include&lt;string&gt;#include&lt;vector&gt;#include&lt;cstring&gt;#include&lt;deque&gt;#define rep(i,n) for(int i=0;i&lt;n;i++)#define pb push_backusing namespace std;const int inf=~0U&gt;&gt;1;const int maxn=50000+1;typedef long long ll;struct node{ int l,r,ch; node(){} node(int _l,int _r,int _ch):l(_l),r(_r),ch(_ch){}};ll Sum[maxn]={0},Dp[maxn];int top=0;int L,n;ll [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/169"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=169"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/169\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=169"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=169"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=169"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}