首页 > 代码库 > codeforce Gym 101102A Coins （01背包变形）
codeforce Gym 101102A Coins （01背包变形）
01背包变形，注意dp过程的时候就需要取膜，否则会出错。
代码如下：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define MAXW 15005#define N 155#define LL long long#define MOD 1000000007int w1[N],w2[N];LL dp1[MAXW],dp2[MAXW];int main(){// freopen("A.in.cpp","r",stdin); int t,n,m,k,W,s,e; int sum1,sum2; LL ans; cin>>t; while(t--) { cin>>n>>m>>k>>W; sum1 = sum2 = 0; for(int i = 0; i < n; i++) { cin>>w1[i]; sum1 += w1[i]; } for(int i = 0; i < m; i++) { cin>>w2[i]; sum2 += w2[i]; } memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); dp1[0] = dp2[0] = 1; for(int i = 0; i < n; i++) { for(int j = sum1; j >= w1[i]; j--) { dp1[j] = (dp1[j]%MOD + dp1[j-w1[i]]%MOD)%MOD;///没有mod就wa } } for(int i = 0; i < m; i++) { for(int j = sum2; j >= w2[i]; j--) { dp2[j] = (dp2[j]%MOD + dp2[j-w2[i]]%MOD)%MOD; } } if((W-k)%2 != 0) s = (W-k)/2+1; else s = (W-k)/2; e = W-s; ans = 0; for(int i = s; i <= e; i++) { ans = (((dp1[i]%MOD)*(dp2[W-i]%MOD))%MOD + ans%MOD) % MOD; } cout<<ans<<endl; } return 0;}
codeforce Gym 101102A Coins （01背包变形）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。