没有限制就是一个完全背包
考虑仅有一个c 的硬币限制为d 枚
正难则反，易得为全部方案数
而不合法的方案使用c 的个数肯定为d+1，d+2..
假设c 强制选d+1 个，则现在所有的方案均为不合法的，也就是
对于多个硬币，只需容斥即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#define LL long long
const int N=100050,n=4;
int c[N],w[N],f[N],val;
LL dp[N];
inline int ()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void init()
{
dp[0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<N-c[i];j++)
dp[j]+=dp[j-c[i]];
}
int main()
{
for(int i=1;i<=n;i++) c[i]=read();
int T=read();
init();
while (T--)
{
for(int i=1;i<=n;i++) w[i]=read();
for(int i=1;i<=n;i++) f[i]=(w[i]+1)*c[i];
int val=read();
LL ans=0;
for(int s=0;s<(1<<n);s++)
{
int num=0,t=1;
for(int i=1;i<=n;i++)
if ((s>>(i-1))&1) num+=f[i],t*=-1;
if (num<=val) ans+=dp[val-num]*t;
}
printf("%lldn",ans);
}
return 0;
}
|
近期评论