{"id":187,"date":"2010-03-25T17:00:00","date_gmt":"2010-03-25T09:00:00","guid":{"rendered":"http:\/\/localhost\/?p=187"},"modified":"2010-03-25T17:00:00","modified_gmt":"2010-03-25T09:00:00","slug":"haoi2008_coin_shopping","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=187","title":{"rendered":"[HAOI2008]\u786c\u5e01\u8d2d\u7269"},"content":{"rendered":"\n

[HAOI2008]\u786c\u5e01\u8d2d\u7269<\/p>\n

Time Limit:10000MS Memory Limit:165536K
Total Submit:11 Accepted:8
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

\u786c\u5e01\u8d2d\u7269
\u4e00\u5171\u67094\u79cd\u786c\u5e01\u3002\u9762\u503c\u5206\u522b\u4e3ac1,c2,c3,c4\u3002\u67d0\u4eba\u53bb\u5546\u5e97\u4e70\u4e1c\u897f\uff0c\u53bb\u4e86tot\u6b21\u3002
\u6bcf\u6b21\u5e26di\u679aci\u786c\u5e01\uff0c\u4e70si\u7684\u4ef7\u503c\u7684\u4e1c\u897f\u3002\u8bf7\u95ee\u6bcf\u6b21\u6709\u591a\u5c11\u79cd\u4ed8\u6b3e\u65b9\u6cd5\u3002 <\/p>\n

Input <\/strong><\/p>\n

\u7b2c\u4e00\u884c
c1,c2,c3,c4,tot
\u4e0b\u9762tot\u884c
d1,d2,d3,d4,s <\/p>\n

Output <\/strong><\/p>\n

\u6bcf\u6b21\u7684\u65b9\u6cd5\u6570 <\/p>\n

Sample Input <\/strong><\/p>\n<\/p>\n

Sample Output <\/strong><\/p>\n<\/p>\n

Source
\u8fd9\u9898\u6709\u70b9NB\u7684\uff0cDP+\u5bb9\u65a5\u539f\u7406\u56e7\u3002\u3002
Code:
<\/strong><\/p>\n

#include<iostream>using namespace std;const int maxn=4,maxs=100000+1;typedef long long ll;ll Dp[maxs]={0};int C[maxn];void Cal(){ Dp[0]=1; for(int i=0;i<maxn;i++) for(int j=C[i];j<maxs;j++) Dp[j]+=Dp[j-C[i]];}int D[maxn];void dfs(int p,int ch,int now,ll&ret){ if(now<0) return; if(p==maxn) { if(ch&1) ret-=Dp[now]; else ret+=Dp[now]; return; } dfs(p+1,ch+1,now-C[p]*(D[p]+1),ret); dfs(p+1,ch,now,ret);}void solve(){ int s;ll ans=0;for(int i=0;i<maxn;i++)cin>>D[i]; cin>>s; dfs(0,0,s,ans); cout<<ans<<endl;}int main(){ \/\/freopen("in","r",stdin); int t; for(int i=0;i<maxn;i++)cin>>C[i];cin>>t; Cal(); while(t–)solve();}427\u6570\u636e\u89c4\u6a21di,s<=100000tot<=10001 2 5 10 23 2 3 1 101000 2 2 2 900 <\/p>\n","protected":false},"excerpt":{"rendered":"

[HAOI2008]\u786c\u5e01\u8d2d\u7269 Time Limit:10000MS Memory Limit:165536KTotal Submit:11 Accepted:8 Case Time Limit:1000MS Description \u786c\u5e01\u8d2d\u7269 \u4e00\u5171\u67094\u79cd\u786c\u5e01\u3002\u9762\u503c\u5206\u522b\u4e3ac1,c2,c3,c4\u3002\u67d0\u4eba\u53bb\u5546\u5e97\u4e70\u4e1c\u897f\uff0c\u53bb\u4e86tot\u6b21\u3002 \u6bcf\u6b21\u5e26di\u679aci\u786c\u5e01\uff0c\u4e70si\u7684\u4ef7\u503c\u7684\u4e1c\u897f\u3002\u8bf7\u95ee\u6bcf\u6b21\u6709\u591a\u5c11\u79cd\u4ed8\u6b3e\u65b9\u6cd5\u3002 Input \u7b2c\u4e00\u884c c1,c2,c3,c4,tot \u4e0b\u9762tot\u884c d1,d2,d3,d4,s Output \u6bcf\u6b21\u7684\u65b9\u6cd5\u6570 Sample Input Sample Output Source \u8fd9\u9898\u6709\u70b9NB\u7684\uff0cDP+\u5bb9\u65a5\u539f\u7406\u56e7\u3002\u3002Code: #include<iostream>using namespace std;const int maxn=4,maxs=100000+1;typedef long long ll;ll Dp[maxs]={0};int C[maxn];void Cal(){ Dp[0]=1; for(int i=0;i<maxn;i++) for(int j=C[i];j<maxs;j++) Dp[j]+=Dp[j-C[i]];}int D[maxn];void dfs(int p,int ch,int now,ll&ret){ if(now<0) return; if(p==maxn) { if(ch&1) ret-=Dp[now]; […]<\/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\/187"}],"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=187"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/187\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=187"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=187"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=187"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}