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 1000000007
int 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 = ;
for(int i = ; i < n; i++)
{
cin>>w1[i];
sum1 += w1[i];
}
for(int i = ; i < m; i++)
{
cin>>w2[i];
sum2 += w2[i];
}
memset(dp1,,sizeof(dp1));
memset(dp2,,sizeof(dp2));
dp1[] = dp2[] = ;
for(int i = ; 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 = ; 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)% != ) s = (W-k)/+;
else s = (W-k)/;
e = W-s;
ans = ;
for(int i = s; i <= e; i++)
{
ans = (((dp1[i]%MOD)*(dp2[W-i]%MOD))%MOD + ans%MOD) % MOD;
}
cout<<ans<<endl;
}
return ;
}
上一篇:git rebase -i 合并多次提交


下一篇:webpack+react+jquery和jquery插件