{"id":353,"date":"2010-08-22T16:34:00","date_gmt":"2010-08-22T08:34:00","guid":{"rendered":"http:\/\/localhost\/?p=353"},"modified":"2010-08-22T16:34:00","modified_gmt":"2010-08-22T08:34:00","slug":"zjoi2004_lunch_lunch","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=353","title":{"rendered":"[Zjoi2004]Lunch \u5348\u9910"},"content":{"rendered":"\n<p>[Zjoi2004]Lunch \u5348\u9910<\/p>\n<p>Time Limit:3000MS&#160; Memory Limit:65536K<br \/>Total Submit:13 Accepted:9 <br \/>Case Time Limit:1000MS<\/p>\n<p><strong>Description <\/strong><\/p>\n<p> \u4e0a\u5348\u7684\u8bad\u7ec3\u7ed3\u675f\u4e86\uff0cTHU  ACM\u5c0f\u7ec4\u96c6\u4f53\u53bb\u5403\u5348\u9910\uff0c\u4ed6\u4eec\u4e00\u884cN\u4eba\u6765\u5230\u4e86\u8457\u540d\u7684\u5341\u98df\u5802\u3002\u8fd9\u91cc\u6709\u4e24\u4e2a\u6253\u996d\u7684\u7a97\u53e3\uff0c\u6bcf\u4e2a\u7a97\u53e3\u540c\u4e00\u65f6\u523b\u53ea\u80fd\u7ed9\u4e00\u4e2a\u4eba\u6253\u996d\u3002\u7531\u4e8e\u6bcf\u4e2a\u4eba\u7684\u53e3\u5473\uff08\u4ee5\u53ca\u80c3\u53e3\uff09\u4e0d \u540c\uff0c\u6240\u4ee5\u4ed6\u4eec\u8981\u5403\u7684\u83dc\u5404\u6709\u4e0d\u540c\uff0c\u6253\u996d\u6240\u8981\u82b1\u8d39\u7684\u65f6\u95f4\u662f\u56e0\u4eba\u800c\u5f02\u7684\u3002\u53e6\u5916\u6bcf\u4e2a\u4eba\u5403\u996d\u7684\u901f\u5ea6\u4e5f\u4e0d\u5c3d\u76f8\u540c\uff0c\u6240\u4ee5\u5403\u996d\u82b1\u8d39\u7684\u65f6\u95f4\u4e5f\u662f\u53ef\u80fd\u6709\u6240\u4e0d\u540c\u7684\u3002 <br \/>THU  ACM\u5c0f\u7ec4\u7684\u5403\u996d\u8ba1\u5212\u662f\u8fd9\u6837\u7684\uff1a\u5148\u628a\u6240\u6709\u7684\u4eba\u5206\u6210\u4e24\u961f\uff0c\u5e76\u5b89\u6392\u597d\u6bcf\u961f\u4e2d\u5404\u4eba\u7684\u6392\u5217\u987a\u5e8f\uff0c\u7136\u540e\u4e00\u53f7\u961f\u4f0d\u5230\u4e00\u53f7\u7a97\u53e3\u53bb\u6392\u961f\u6253\u996d\uff0c\u4e8c\u53f7\u961f\u4f0d\u5230\u4e8c\u53f7\u7a97\u53e3\u53bb\u6392\u961f\u6253 \u996d\u3002\u6bcf\u4e2a\u4eba\u6253\u5b8c\u996d\u540e\u7acb\u523b\u5f00\u59cb\u5403\uff0c\u6240\u6709\u4eba\u90fd\u5403\u5b8c\u996d\u540e\u7acb\u523b\u96c6\u5408\u53bb\u516d\u6559\u5730\u4e0b\u5ba4\u8fdb\u884c\u4e0b\u5348\u7684\u8bad\u7ec3\u3002 <br \/>\u73b0\u5728\u7ed9\u5b9a\u4e86\u6bcf\u4e2a\u4eba\u7684\u6253\u996d\u65f6\u95f4\u548c\u5403\u996d\u65f6\u95f4\uff0c\u8981\u6c42\u5b89\u6392\u4e00\u79cd\u6700\u4f73\u7684\u5206\u961f\u548c\u6392\u961f\u65b9\u6848\u4f7f\u5f97\u6240\u6709\u4eba\u90fd\u5403\u5b8c\u996d\u7684\u65f6\u95f4\u5c3d\u91cf\u65e9\u3002 <br \/>\u5047\u8bbeTHU  ACM\u5c0f\u7ec4\u5728\u65f6\u523b0\u5230\u8fbe\u5341\u98df\u5802\uff0c\u800c\u4e14\u98df\u5802\u91cc\u9762\u6ca1\u6709\u5176\u4ed6\u5403\u996d\u7684\u540c\u5b66\uff08\u53ea\u6709\u6253\u996d\u7684\u5e08\u5085\uff09\u3002\u6bcf\u4e2a\u4eba\u5fc5\u987b\u800c\u4e14\u53ea\u80fd\u88ab\u5206\u5728\u4e00\u4e2a\u961f\u4f0d\u91cc\u3002\u4e24\u4e2a\u7a97\u53e3\u662f\u5e76\u884c\u64cd\u4f5c\u4e92\u4e0d\u5f71\u54cd \u7684\uff0c\u800c\u4e14\u6bcf\u4e2a\u4eba\u6253\u996d\u7684\u65f6\u95f4\u662f\u548c\u7a97\u53e3\u65e0\u5173\u7684\uff0c\u6253\u5b8c\u996d\u4e4b\u540e\u7acb\u523b\u5c31\u5f00\u59cb\u5403\u996d\uff0c\u4e2d\u95f4\u6ca1\u6709\u5ef6\u8fdf\u3002 <br \/>\u73b0\u5728\u7ed9\u5b9aN\u4e2a\u4eba\u5404\u81ea\u7684\u6253\u996d\u65f6\u95f4\u548c\u5403\u996d\u65f6\u95f4\uff0c\u8981\u6c42\u8f93\u51fa\u6700\u4f73\u65b9\u6848\u4e0b\u6240\u6709\u4eba\u5403\u5b8c\u996d\u7684\u65f6\u523b\u3002 <\/p>\n<p><strong>Input <\/strong><\/p>\n<p>\u7b2c\u4e00\u884c\u4e00\u4e2a\u6574\u6570N\uff0c\u4ee3\u8868\u603b\u5171\u6709N\u4e2a\u4eba\u3002 <br \/>\u4ee5\u4e0bN\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u6574\u6570 Ai\uff0cBi\u3002\u4f9d\u6b21\u4ee3\u8868\u7b2ci\u4e2a\u4eba\u7684\u6253\u996d\u65f6\u95f4\u548c\u5403\u996d\u65f6\u95f4\u3002 <\/p>\n<p><\/p>\n<p><strong>Output <\/strong><\/p>\n<p> \u4e00\u4e2a\u6574\u6570T\uff0c\u4ee3\u8868\u6240\u6709\u4eba\u5403\u5b8c\u996d\u7684\u6700\u65e9\u65f6\u523b\u3002 <\/p>\n<p><strong>Sample Input <\/strong><\/p>\n<p>5<br \/>2 2<br \/>7 7<br \/>1 3<br \/>6 4<br \/>8 5<\/p>\n<p><strong>Sample Output <\/strong><\/p>\n<p>17<\/p>\n<p><strong>Hint <\/strong><\/p>\n<p> \u65b9\u6848\u5982\u4e0b\uff1a <\/p>\n<p>\u7a97\u53e31\uff1a      \u7a97\u53e32\uff1a <br \/>7 7               1 3 <br \/>6 4      8 5 <br \/>2 2 <\/p>\n<p>\u3010\u9650\u5236\u3011 <br \/>\u6240\u6709\u8f93\u5165\u6570\u636e\u5747\u4e3a\u4e0d\u8d85\u8fc7200\u7684\u6b63\u6574\u6570\u3002 <\/p>\n<p><strong>Source <\/strong><\/p>\n<p>\u989d\u3002\u8fd9\u4e2a\u9898\u76ee\u8fd8\u4e0d\u9519\u3002\u3002\u633a\u6709\u610f\u601d\u7684\u3002\u3002<br \/>\u9996\u5148\u4e00\u770b\u5230\u8fd9\u7ecf\u5178\u7684\u6a21\u578b\uff0c\u53ef\u4ee5B\u5927\u7684\u8981\u5728\u524d\u9762\u3002\u3002<br \/>\u7136\u540e\u5c31\u53ef\u4ee5\u52a8\u5f52\u4e86\u3002\u3002<br \/>\u5148\u6309B\u964d\u5e8f\u6392\u5e8f\u3002\u3002<br \/>\u7528Dp[i][j]\u8868\u793a\u524di\u4e2a\uff0c\u7b2c\u4e00\u4e2a\u961f\u7684\u5403\u996d\u65f6\u95f4\u548c\u4e3aj\u7684\u6700\u4f18\u503c\u3002\u3002<br \/>Code\uff1a<br \/>#include &lt;vector&gt;<br \/>#include &lt;algorithm&gt;<br \/>#include &lt;utility&gt;<br \/>#include &lt;iostream&gt;<br \/>#include &lt;cstdio&gt;<br \/>#include &lt;cmath&gt;<br \/>#include &lt;cstdlib&gt;<br \/>#include &lt;set&gt;<br \/>#include &lt;map&gt;<br \/>#include &lt;cstring&gt;<br \/>#include &lt;time.h&gt;<br \/>#define rep(i,n) for(int i=0;i&lt;n;i++)<br \/>const int inf=~0U&gt;&gt;1,maxn=201;<br \/>using namespace std;<br \/>int A[maxn],B[maxn],P[maxn],n;<br \/>bool cmp(int i,int j)<br \/>{<br \/>    return B[i]&gt;B[j];<br \/>}<br \/>int Dp[2][maxn*maxn];<br \/>inline void Update(int&amp;t,int c)<br \/>{<br \/>    if(t==-1||t&gt;c)t=c;<br \/>}<br \/>int main()<br \/>{<br \/>    \/\/freopen(&quot;in&quot;,&quot;r&quot;,stdin);<br \/>    cin&gt;&gt;n;<br \/>    rep(i,n)<br \/>    {<br \/>        cin&gt;&gt;A[i]&gt;&gt;B[i];<br \/>        P[i]=i;<br \/>    }<br \/>    sort(P,P+n,cmp);<br \/>    int now=0,next=1,sum=0;<br \/>    memset(Dp[next],-1,sizeof Dp[next]);<br \/>    Dp[next][0]=0;<br \/>    for(int i=0;i&lt;n;i++)<br \/>    {<br \/>        int t=P[i],c,first,second,nc;<br \/>        swap(now,next);<br \/>        memset(Dp[next],-1,sizeof Dp[next]);<br \/>        rep(j,sum+1)<br \/>            if((c=Dp[now][j])!=-1)<br \/>            {<br \/>                first=j;<br \/>                second=sum-j;<br \/>                \/\/Put it In First Queue<br \/>                nc=max(first+A[t]+B[t],c);<br \/>                Update(Dp[next][j+A[t]],nc);<br \/>                \/\/Put it In Second Queue<br \/>                nc=max(second+A[t]+B[t],c);<br \/>                Update(Dp[next][j],nc);<br \/>            }<br \/>        sum+=A[t];<br \/>    }<br \/>    int ans=inf;<br \/>    rep(i,sum+1)if(Dp[next][i]!=-1)ans=min(ans,Dp[next][i]);<br \/>    cout&lt;&lt;ans&lt;&lt;endl;<br \/>} <\/p>\n","protected":false},"excerpt":{"rendered":"<p>[Zjoi2004]Lunch \u5348\u9910 Time Limit:3000MS&#160; Memory Limit:65536KTotal Submit:13 Accepted:9 Case Time Limit:1000MS Description \u4e0a\u5348\u7684\u8bad\u7ec3\u7ed3\u675f\u4e86\uff0cTHU ACM\u5c0f\u7ec4\u96c6\u4f53\u53bb\u5403\u5348\u9910\uff0c\u4ed6\u4eec\u4e00\u884cN\u4eba\u6765\u5230\u4e86\u8457\u540d\u7684\u5341\u98df\u5802\u3002\u8fd9\u91cc\u6709\u4e24\u4e2a\u6253\u996d\u7684\u7a97\u53e3\uff0c\u6bcf\u4e2a\u7a97\u53e3\u540c\u4e00\u65f6\u523b\u53ea\u80fd\u7ed9\u4e00\u4e2a\u4eba\u6253\u996d\u3002\u7531\u4e8e\u6bcf\u4e2a\u4eba\u7684\u53e3\u5473\uff08\u4ee5\u53ca\u80c3\u53e3\uff09\u4e0d \u540c\uff0c\u6240\u4ee5\u4ed6\u4eec\u8981\u5403\u7684\u83dc\u5404\u6709\u4e0d\u540c\uff0c\u6253\u996d\u6240\u8981\u82b1\u8d39\u7684\u65f6\u95f4\u662f\u56e0\u4eba\u800c\u5f02\u7684\u3002\u53e6\u5916\u6bcf\u4e2a\u4eba\u5403\u996d\u7684\u901f\u5ea6\u4e5f\u4e0d\u5c3d\u76f8\u540c\uff0c\u6240\u4ee5\u5403\u996d\u82b1\u8d39\u7684\u65f6\u95f4\u4e5f\u662f\u53ef\u80fd\u6709\u6240\u4e0d\u540c\u7684\u3002 THU ACM\u5c0f\u7ec4\u7684\u5403\u996d\u8ba1\u5212\u662f\u8fd9\u6837\u7684\uff1a\u5148\u628a\u6240\u6709\u7684\u4eba\u5206\u6210\u4e24\u961f\uff0c\u5e76\u5b89\u6392\u597d\u6bcf\u961f\u4e2d\u5404\u4eba\u7684\u6392\u5217\u987a\u5e8f\uff0c\u7136\u540e\u4e00\u53f7\u961f\u4f0d\u5230\u4e00\u53f7\u7a97\u53e3\u53bb\u6392\u961f\u6253\u996d\uff0c\u4e8c\u53f7\u961f\u4f0d\u5230\u4e8c\u53f7\u7a97\u53e3\u53bb\u6392\u961f\u6253 \u996d\u3002\u6bcf\u4e2a\u4eba\u6253\u5b8c\u996d\u540e\u7acb\u523b\u5f00\u59cb\u5403\uff0c\u6240\u6709\u4eba\u90fd\u5403\u5b8c\u996d\u540e\u7acb\u523b\u96c6\u5408\u53bb\u516d\u6559\u5730\u4e0b\u5ba4\u8fdb\u884c\u4e0b\u5348\u7684\u8bad\u7ec3\u3002 \u73b0\u5728\u7ed9\u5b9a\u4e86\u6bcf\u4e2a\u4eba\u7684\u6253\u996d\u65f6\u95f4\u548c\u5403\u996d\u65f6\u95f4\uff0c\u8981\u6c42\u5b89\u6392\u4e00\u79cd\u6700\u4f73\u7684\u5206\u961f\u548c\u6392\u961f\u65b9\u6848\u4f7f\u5f97\u6240\u6709\u4eba\u90fd\u5403\u5b8c\u996d\u7684\u65f6\u95f4\u5c3d\u91cf\u65e9\u3002 \u5047\u8bbeTHU ACM\u5c0f\u7ec4\u5728\u65f6\u523b0\u5230\u8fbe\u5341\u98df\u5802\uff0c\u800c\u4e14\u98df\u5802\u91cc\u9762\u6ca1\u6709\u5176\u4ed6\u5403\u996d\u7684\u540c\u5b66\uff08\u53ea\u6709\u6253\u996d\u7684\u5e08\u5085\uff09\u3002\u6bcf\u4e2a\u4eba\u5fc5\u987b\u800c\u4e14\u53ea\u80fd\u88ab\u5206\u5728\u4e00\u4e2a\u961f\u4f0d\u91cc\u3002\u4e24\u4e2a\u7a97\u53e3\u662f\u5e76\u884c\u64cd\u4f5c\u4e92\u4e0d\u5f71\u54cd \u7684\uff0c\u800c\u4e14\u6bcf\u4e2a\u4eba\u6253\u996d\u7684\u65f6\u95f4\u662f\u548c\u7a97\u53e3\u65e0\u5173\u7684\uff0c\u6253\u5b8c\u996d\u4e4b\u540e\u7acb\u523b\u5c31\u5f00\u59cb\u5403\u996d\uff0c\u4e2d\u95f4\u6ca1\u6709\u5ef6\u8fdf\u3002 \u73b0\u5728\u7ed9\u5b9aN\u4e2a\u4eba\u5404\u81ea\u7684\u6253\u996d\u65f6\u95f4\u548c\u5403\u996d\u65f6\u95f4\uff0c\u8981\u6c42\u8f93\u51fa\u6700\u4f73\u65b9\u6848\u4e0b\u6240\u6709\u4eba\u5403\u5b8c\u996d\u7684\u65f6\u523b\u3002 Input \u7b2c\u4e00\u884c\u4e00\u4e2a\u6574\u6570N\uff0c\u4ee3\u8868\u603b\u5171\u6709N\u4e2a\u4eba\u3002 \u4ee5\u4e0bN\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u6574\u6570 Ai\uff0cBi\u3002\u4f9d\u6b21\u4ee3\u8868\u7b2ci\u4e2a\u4eba\u7684\u6253\u996d\u65f6\u95f4\u548c\u5403\u996d\u65f6\u95f4\u3002 Output \u4e00\u4e2a\u6574\u6570T\uff0c\u4ee3\u8868\u6240\u6709\u4eba\u5403\u5b8c\u996d\u7684\u6700\u65e9\u65f6\u523b\u3002 Sample Input 52 27 71 36 48 5 Sample Output 17 Hint \u65b9\u6848\u5982\u4e0b\uff1a \u7a97\u53e31\uff1a \u7a97\u53e32\uff1a 7 7 1 3 6 4 8 5 2 2 \u3010\u9650\u5236\u3011 [&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\/353"}],"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=353"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/353\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=353"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=353"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=353"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}