{"id":170,"date":"2010-03-20T15:02:00","date_gmt":"2010-03-20T07:02:00","guid":{"rendered":"http:\/\/localhost\/?p=170"},"modified":"2010-03-20T15:02:00","modified_gmt":"2010-03-20T07:02:00","slug":"zjoi2007_warehouse_building","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=170","title":{"rendered":"[ZJOI2007]\u4ed3\u5e93\u5efa\u8bbe"},"content":{"rendered":"\n<p>[ZJOI2007]\u4ed3\u5e93\u5efa\u8bbe<\/p>\n<p>Time Limit:10000MS&#160; Memory Limit:165536K<br \/>Total Submit:51 Accepted:28 <br \/>Case Time Limit:3000MS<\/p>\n<p><strong>Description <\/strong><\/p>\n<p> L\u516c\u53f8\u6709N\u4e2a\u5de5\u5382\uff0c\u7531\u9ad8\u5230\u5e95\u5206\u5e03\u5728\u4e00\u5ea7\u5c71\u4e0a\u3002\u5982\u56fe\u6240\u793a\uff0c\u5de5\u53821\u5728\u5c71\u9876\uff0c\u5de5\u5382N\u5728\u5c71\u811a\u3002 <\/p>\n<p>\u7531\u4e8e\u8fd9\u5ea7\u5c71\u5904\u4e8e\u9ad8\u539f\u5185\u9646\u5730\u533a\uff08\u5e72\u71e5\u5c11\u96e8\uff09\uff0cL\u516c\u53f8\u4e00\u822c\u628a\u4ea7\u54c1\u76f4\u63a5\u5806\u653e\u5728\u9732\u5929\uff0c\u4ee5\u8282\u7701\u8d39\u7528\u3002\u7a81\u7136\u6709\u4e00\u5929\uff0cL\u516c\u53f8\u7684\u603b\u88c1L\u5148\u751f\u63a5\u5230\u6c14\u8c61\u90e8\u95e8\u7684\u7535\u8bdd\uff0c\u88ab \u544a\u77e5\u4e09\u5929\u4e4b\u540e\u5c06\u6709\u4e00\u573a\u66b4\u96e8\uff0c\u4e8e\u662fL\u5148\u751f\u51b3\u5b9a\u7d27\u6025\u5728\u67d0\u4e9b\u5de5\u5382\u5efa\u7acb\u4e00\u4e9b\u4ed3\u5e93\u4ee5\u514d\u4ea7\u54c1\u88ab\u6dcb\u574f\u3002 <br \/>\u7531\u4e8e\u5730\u5f62\u7684\u4e0d\u540c\uff0c\u5728\u4e0d\u540c\u5de5\u5382\u5efa\u7acb\u4ed3\u5e93\u7684\u8d39\u7528\u53ef\u80fd\u662f\u4e0d\u540c\u7684\u3002\u7b2ci\u4e2a\u5de5\u5382\u76ee\u524d\u5df2\u6709\u6210\u54c1Pi\u4ef6\uff0c\u5728\u7b2ci\u4e2a\u5de5\u5382\u4f4d\u7f6e\u5efa\u7acb\u4ed3\u5e93\u7684\u8d39\u7528\u662fCi\u3002\u5bf9\u4e8e\u6ca1\u6709\u5efa\u7acb\u4ed3 \u5e93\u7684\u5de5\u5382\uff0c\u5176\u4ea7\u54c1\u5e94\u88ab\u8fd0\u5f80\u5176\u4ed6\u7684\u4ed3\u5e93\u8fdb\u884c\u50a8\u85cf\uff0c\u800c\u7531\u4e8eL\u516c\u53f8\u4ea7\u54c1\u7684\u5bf9\u5916\u9500\u552e\u5904\u8bbe\u7f6e\u5728\u5c71\u811a\u7684\u5de5\u5382N\uff0c\u6545\u4ea7\u54c1\u53ea\u80fd\u5f80\u5c71\u4e0b\u8fd0\uff08\u5373\u53ea\u80fd\u8fd0\u5f80\u7f16\u53f7\u66f4\u5927\u7684\u5de5\u5382\u7684\u4ed3 \u5e93\uff09\uff0c\u5f53\u7136\u8fd0\u9001\u4ea7\u54c1\u4e5f\u662f\u9700\u8981\u8d39\u7528\u7684\uff0c\u5047\u8bbe\u4e00\u4ef6\u4ea7\u54c1\u8fd0\u90011\u4e2a\u5355\u4f4d\u8ddd\u79bb\u7684\u8d39\u7528\u662f1\u3002\u5047\u8bbe\u5efa\u7acb\u7684\u4ed3\u5e93\u5bb9\u91cf\u90fd\u90fd\u662f\u8db3\u591f\u5927\u7684\uff0c\u53ef\u4ee5\u5bb9\u4e0b\u6240\u6709\u7684\u4ea7\u54c1\u3002 <br \/>\u4f60\u5c06\u5f97\u5230\u4ee5\u4e0b\u6570\u636e\uff1a <br \/>&#61548; \u5de5\u5382i\u8ddd\u79bb\u5de5\u53821\u7684\u8ddd\u79bbXi\uff08\u5176\u4e2dX1=0\uff09; <br \/>&#61548; \u5de5\u5382i\u76ee\u524d\u5df2\u6709\u6210\u54c1\u6570\u91cfPi; <br \/>&#61548; \u5728\u5de5\u5382i\u5efa\u7acb\u4ed3\u5e93\u7684\u8d39\u7528Ci; <\/p>\n<p>\u8bf7\u4f60\u5e2e\u52a9L\u516c\u53f8\u5bfb\u627e\u4e00\u4e2a\u4ed3\u5e93\u5efa\u8bbe\u7684\u65b9\u6848\uff0c\u4f7f\u5f97\u603b\u7684\u8d39\u7528\uff08\u5efa\u9020\u8d39\u7528+\u8fd0\u8f93\u8d39\u7528\uff09\u6700\u5c0f\u3002 <\/p>\n<p><strong>Input <\/strong><\/p>\n<p> \u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570N\uff0c\u8868\u793a\u5de5\u5382\u7684\u4e2a\u6570\u3002\u63a5\u4e0b\u6765N\u884c\u6bcf\u884c\u5305\u542b\u4e24\u4e2a\u6574\u6570Xi, Pi, Ci, \u610f\u4e49\u5982\u9898\u4e2d\u6240\u8ff0\u3002 <\/p>\n<p><strong>Output <\/strong><\/p>\n<p> \u4ec5\u5305\u542b\u4e00\u4e2a\u6574\u6570\uff0c\u4e3a\u53ef\u4ee5\u627e\u5230\u6700\u4f18\u65b9\u6848\u7684\u8d39\u7528\u3002 <\/p>\n<p><strong>Sample Input <\/strong><\/p>\n<p>3<br \/>0 5 10<br \/>5 3 100<br \/>9 6 10<\/p>\n<p><strong>Sample Output <\/strong><\/p>\n<p>32<\/p>\n<p><strong>Hint <\/strong><\/p>\n<p> \u5728\u5de5\u53821\u548c\u5de5\u53823\u5efa\u7acb\u4ed3\u5e93\uff0c\u5efa\u7acb\u8d39\u7528\u4e3a10+10=20\uff0c\u8fd0\u8f93\u8d39\u7528\u4e3a(9-5)*3 = 12\uff0c\u603b\u8d39\u752832\u3002 <br \/>\u5982\u679c\u4ec5\u5728\u5de5\u53823\u5efa\u7acb\u4ed3\u5e93\uff0c\u5efa\u7acb\u8d39\u7528\u4e3a10\uff0c\u8fd0\u8f93\u8d39\u7528\u4e3a(9-0)*5+(9-5)*3=57\uff0c\u603b\u8d39\u752867\uff0c\u4e0d\u5982\u524d\u8005\u4f18\u3002 <br \/>\u3010\u6570\u636e\u89c4\u6a21\u3011 <br \/>\u5bf9\u4e8e20%\u7684\u6570\u636e\uff0c N \u2264500\uff1b <br \/>\u5bf9\u4e8e40%\u7684\u6570\u636e\uff0c N \u226410000\uff1b <br \/>\u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c N \u22641000000\u3002  <br \/>\u6240\u6709\u7684Xi, Pi, Ci\u5747\u572832\u4f4d\u5e26\u7b26\u53f7\u6574\u6570\u4ee5\u5185\uff0c\u4fdd\u8bc1\u4e2d\u95f4\u8ba1\u7b97\u7ed3\u679c\u4e0d\u8d85\u8fc764\u4f4d\u5e26\u7b26\u53f7\u6574\u6570\u3002 <\/p>\n<p><\/p>\n<p><strong>Source <\/strong><\/p>\n<p>\u8fd9\u9053\u9898\u76ee\u5f88\u660e\u663e\u8fd8\u662f\u51b3\u7b56\u5355\u8c03\u6027\u3002\u3002\u8ddftoy\u4e00\u6478\u4e00\u6837\u4e00\u6837\u7684\u505a\u6cd5\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u4e0d\u8fc7longlong\u4e0a\u9762\u7ea0\u7ed3\u4e86\u534a\u5929\u56e7\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,maxn=1000000+1;<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 \/>typedef long long ll;<br \/>int C[maxn],X[maxn],n;<br \/>ll SP[maxn]={0},SXP[maxn]={0},Dp[maxn];<br \/>ll Cost(int l,int r)<br \/>{<br \/>    return (SP[r]-SP[l-1])*X[r]-(SXP[r]-SXP[l-1])+C[r];<br \/>}<br \/>ll Get(int i,int j)<br \/>{<br \/>    return Dp[j]+Cost(j+1,i);<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 \/>    #undef check<br \/>    return l;<br \/>}<br \/>void Init()<br \/>{<br \/>    int x,p;<br \/>    scanf(&quot;%d&quot;,&amp;n);<br \/>    for(int i=1;i&lt;=n;i++)<br \/>    {<br \/>        scanf(&quot;%d %d %d&quot;,&amp;x,&amp;p,C+i);<br \/>        SP[i]=SP[i-1]+p;SXP[i]=SXP[i-1]+ll(x)*p;X[i]=x;<br \/>    }<br \/>}<br \/>void Work()<br \/>{<br \/>    deque&lt;node&gt; D;<br \/>    Dp[0]=0;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 \/>        int e;node t;<br \/>        while(D.size())<br \/>        {<br \/>            t=D.back();<br \/>            if(Get(t.l,i)&lt;=Get(t.l,t.ch))<br \/>                D.pop_back();<br \/>            else<br \/>            {<br \/>                e=binary(t,i);<br \/>                D.back().r=e;<br \/>                break;<br \/>            }<br \/>        }<br \/>        if(D.size()==0) 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>[ZJOI2007]\u4ed3\u5e93\u5efa\u8bbe Time Limit:10000MS&#160; Memory Limit:165536KTotal Submit:51 Accepted:28 Case Time Limit:3000MS Description L\u516c\u53f8\u6709N\u4e2a\u5de5\u5382\uff0c\u7531\u9ad8\u5230\u5e95\u5206\u5e03\u5728\u4e00\u5ea7\u5c71\u4e0a\u3002\u5982\u56fe\u6240\u793a\uff0c\u5de5\u53821\u5728\u5c71\u9876\uff0c\u5de5\u5382N\u5728\u5c71\u811a\u3002 \u7531\u4e8e\u8fd9\u5ea7\u5c71\u5904\u4e8e\u9ad8\u539f\u5185\u9646\u5730\u533a\uff08\u5e72\u71e5\u5c11\u96e8\uff09\uff0cL\u516c\u53f8\u4e00\u822c\u628a\u4ea7\u54c1\u76f4\u63a5\u5806\u653e\u5728\u9732\u5929\uff0c\u4ee5\u8282\u7701\u8d39\u7528\u3002\u7a81\u7136\u6709\u4e00\u5929\uff0cL\u516c\u53f8\u7684\u603b\u88c1L\u5148\u751f\u63a5\u5230\u6c14\u8c61\u90e8\u95e8\u7684\u7535\u8bdd\uff0c\u88ab \u544a\u77e5\u4e09\u5929\u4e4b\u540e\u5c06\u6709\u4e00\u573a\u66b4\u96e8\uff0c\u4e8e\u662fL\u5148\u751f\u51b3\u5b9a\u7d27\u6025\u5728\u67d0\u4e9b\u5de5\u5382\u5efa\u7acb\u4e00\u4e9b\u4ed3\u5e93\u4ee5\u514d\u4ea7\u54c1\u88ab\u6dcb\u574f\u3002 \u7531\u4e8e\u5730\u5f62\u7684\u4e0d\u540c\uff0c\u5728\u4e0d\u540c\u5de5\u5382\u5efa\u7acb\u4ed3\u5e93\u7684\u8d39\u7528\u53ef\u80fd\u662f\u4e0d\u540c\u7684\u3002\u7b2ci\u4e2a\u5de5\u5382\u76ee\u524d\u5df2\u6709\u6210\u54c1Pi\u4ef6\uff0c\u5728\u7b2ci\u4e2a\u5de5\u5382\u4f4d\u7f6e\u5efa\u7acb\u4ed3\u5e93\u7684\u8d39\u7528\u662fCi\u3002\u5bf9\u4e8e\u6ca1\u6709\u5efa\u7acb\u4ed3 \u5e93\u7684\u5de5\u5382\uff0c\u5176\u4ea7\u54c1\u5e94\u88ab\u8fd0\u5f80\u5176\u4ed6\u7684\u4ed3\u5e93\u8fdb\u884c\u50a8\u85cf\uff0c\u800c\u7531\u4e8eL\u516c\u53f8\u4ea7\u54c1\u7684\u5bf9\u5916\u9500\u552e\u5904\u8bbe\u7f6e\u5728\u5c71\u811a\u7684\u5de5\u5382N\uff0c\u6545\u4ea7\u54c1\u53ea\u80fd\u5f80\u5c71\u4e0b\u8fd0\uff08\u5373\u53ea\u80fd\u8fd0\u5f80\u7f16\u53f7\u66f4\u5927\u7684\u5de5\u5382\u7684\u4ed3 \u5e93\uff09\uff0c\u5f53\u7136\u8fd0\u9001\u4ea7\u54c1\u4e5f\u662f\u9700\u8981\u8d39\u7528\u7684\uff0c\u5047\u8bbe\u4e00\u4ef6\u4ea7\u54c1\u8fd0\u90011\u4e2a\u5355\u4f4d\u8ddd\u79bb\u7684\u8d39\u7528\u662f1\u3002\u5047\u8bbe\u5efa\u7acb\u7684\u4ed3\u5e93\u5bb9\u91cf\u90fd\u90fd\u662f\u8db3\u591f\u5927\u7684\uff0c\u53ef\u4ee5\u5bb9\u4e0b\u6240\u6709\u7684\u4ea7\u54c1\u3002 \u4f60\u5c06\u5f97\u5230\u4ee5\u4e0b\u6570\u636e\uff1a &#61548; \u5de5\u5382i\u8ddd\u79bb\u5de5\u53821\u7684\u8ddd\u79bbXi\uff08\u5176\u4e2dX1=0\uff09; &#61548; \u5de5\u5382i\u76ee\u524d\u5df2\u6709\u6210\u54c1\u6570\u91cfPi; &#61548; \u5728\u5de5\u5382i\u5efa\u7acb\u4ed3\u5e93\u7684\u8d39\u7528Ci; \u8bf7\u4f60\u5e2e\u52a9L\u516c\u53f8\u5bfb\u627e\u4e00\u4e2a\u4ed3\u5e93\u5efa\u8bbe\u7684\u65b9\u6848\uff0c\u4f7f\u5f97\u603b\u7684\u8d39\u7528\uff08\u5efa\u9020\u8d39\u7528+\u8fd0\u8f93\u8d39\u7528\uff09\u6700\u5c0f\u3002 Input \u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u6574\u6570N\uff0c\u8868\u793a\u5de5\u5382\u7684\u4e2a\u6570\u3002\u63a5\u4e0b\u6765N\u884c\u6bcf\u884c\u5305\u542b\u4e24\u4e2a\u6574\u6570Xi, Pi, Ci, \u610f\u4e49\u5982\u9898\u4e2d\u6240\u8ff0\u3002 Output \u4ec5\u5305\u542b\u4e00\u4e2a\u6574\u6570\uff0c\u4e3a\u53ef\u4ee5\u627e\u5230\u6700\u4f18\u65b9\u6848\u7684\u8d39\u7528\u3002 Sample Input 30 5 105 3 1009 6 10 Sample Output 32 Hint \u5728\u5de5\u53821\u548c\u5de5\u53823\u5efa\u7acb\u4ed3\u5e93\uff0c\u5efa\u7acb\u8d39\u7528\u4e3a10+10=20\uff0c\u8fd0\u8f93\u8d39\u7528\u4e3a(9-5)*3 = 12\uff0c\u603b\u8d39\u752832\u3002 \u5982\u679c\u4ec5\u5728\u5de5\u53823\u5efa\u7acb\u4ed3\u5e93\uff0c\u5efa\u7acb\u8d39\u7528\u4e3a10\uff0c\u8fd0\u8f93\u8d39\u7528\u4e3a(9-0)*5+(9-5)*3=57\uff0c\u603b\u8d39\u752867\uff0c\u4e0d\u5982\u524d\u8005\u4f18\u3002 \u3010\u6570\u636e\u89c4\u6a21\u3011 \u5bf9\u4e8e20%\u7684\u6570\u636e\uff0c N \u2264500\uff1b \u5bf9\u4e8e40%\u7684\u6570\u636e\uff0c N [&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\/170"}],"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=170"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/170\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=170"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=170"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}