{"id":248,"date":"2010-05-14T12:55:00","date_gmt":"2010-05-14T04:55:00","guid":{"rendered":"http:\/\/localhost\/?p=248"},"modified":"2010-05-14T12:55:00","modified_gmt":"2010-05-14T04:55:00","slug":"rqnoj_multiplayer_backpack","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=248","title":{"rendered":"RQNOJ \u591a\u4eba\u80cc\u5305"},"content":{"rendered":"\n<p><a target=\"_blank\" href=\"http:\/\/www.rqnoj.cn\/Problem_123.html\">www.rqnoj.cn\/Problem_123.html<\/a><br \/>\u8fd9\u9053\u9898\u76ee\u5b9e\u9645\u4e0a\u610f\u601d\u5c31\u662f\u6c42\u524dK\u4f18\u89e3\uff0c\u6548\u4eff\u4e00\u822c\u7684\u52a8\u6001\u89c4\u5212\uff0c\u53ef\u4ee5\u5f88\u65b9\u4fbf\u7684\u641e\u5b9a\u8fd9\u4e2a\u3002\u3002\u53ea\u662f\u8f6c\u79fb\u7684\u65f6\u5019\u66f4\u65b0\u7684\u662f\u4e00\u4e2a\u961f\u5217\u3002\u3002<br \/>Code\uff1a<\/p>\n<p>#include&lt;cstdio&gt;#include&lt;algorithm&gt;#include&lt;iostream&gt;#define rep(i,n) for(int i=0;i&lt;n;i++)const int maxk=50+1,maxv=5000+1,maxn=200,inf=~0U&gt;&gt;1;using namespace std;int k,v,n;struct Thing{    int w,v;}T[maxn];int tmp[maxk];struct State{    int n,A[maxk];    State(){n=0;}    void put(int x){A[n++]=x;}    void Update(State&amp;s,int v)    {        int m=min(k,s.n+n),i=0,j=0;        #define get(i) (s.A[i]+v)        A[n]=-inf;s.A[s.n]=-inf;        rep(o,m)        {            if(A[i]&gt;get(j))                tmp[o]=A[i],i++;            else                tmp[o]=get(j),j++;        }        memcpy(A,tmp,sizeof(int)*m);        n=m;    }}Dp[maxv];void Init(){    scanf(&quot;%d%d%d&quot;,&amp;k,&amp;v,&amp;n);    rep(i,n)scanf(&quot;%d%d&quot;,&amp;T[i].w,&amp;T[i].v);}void Solve(){    Dp[0].put(0);    rep(i,n)    {        for(int j=v;j&gt;=T[i].w;j&#8211;)            Dp[j].Update(Dp[j-T[i].w],T[i].v);    }    int ans=0;    rep(i,Dp[v].n)ans+=Dp[v].A[i];    cout&lt;&lt;ans&lt;&lt;endl;}int main(){    \/\/freopen(&quot;in&quot;,&quot;r&quot;,stdin);    Init();    Solve();} <\/p>\n","protected":false},"excerpt":{"rendered":"<p>www.rqnoj.cn\/Problem_123.html\u8fd9\u9053\u9898\u76ee\u5b9e\u9645\u4e0a\u610f\u601d\u5c31\u662f\u6c42\u524dK\u4f18\u89e3\uff0c\u6548\u4eff\u4e00\u822c\u7684\u52a8\u6001\u89c4\u5212\uff0c\u53ef\u4ee5\u5f88\u65b9\u4fbf\u7684\u641e\u5b9a\u8fd9\u4e2a\u3002\u3002\u53ea\u662f\u8f6c\u79fb\u7684\u65f6\u5019\u66f4\u65b0\u7684\u662f\u4e00\u4e2a\u961f\u5217\u3002\u3002Code\uff1a #include&lt;cstdio&gt;#include&lt;algorithm&gt;#include&lt;iostream&gt;#define rep(i,n) for(int i=0;i&lt;n;i++)const int maxk=50+1,maxv=5000+1,maxn=200,inf=~0U&gt;&gt;1;using namespace std;int k,v,n;struct Thing{ int w,v;}T[maxn];int tmp[maxk];struct State{ int n,A[maxk]; State(){n=0;} void put(int x){A[n++]=x;} void Update(State&amp;s,int v) { int m=min(k,s.n+n),i=0,j=0; #define get(i) (s.A[i]+v) A[n]=-inf;s.A[s.n]=-inf; rep(o,m) { if(A[i]&gt;get(j)) tmp[o]=A[i],i++; else tmp[o]=get(j),j++; } memcpy(A,tmp,sizeof(int)*m); n=m; }}Dp[maxv];void Init(){ scanf(&quot;%d%d%d&quot;,&amp;k,&amp;v,&amp;n); rep(i,n)scanf(&quot;%d%d&quot;,&amp;T[i].w,&amp;T[i].v);}void Solve(){ Dp[0].put(0); rep(i,n) { for(int j=v;j&gt;=T[i].w;j&#8211;) Dp[j].Update(Dp[j-T[i].w],T[i].v); } int ans=0; rep(i,Dp[v].n)ans+=Dp[v].A[i]; [&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\/248"}],"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=248"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/248\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=248"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=248"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=248"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}