即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

BZOJ 1042 [HAOI2008] 硬币购物

编程语言 SenyeLicone 11℃ 0评论
本文目录
[隐藏]

1.Description

  硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买s


i的价值的东西。请问每次有多少种付款方法。

2.Input

  第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000

3.Output

  每次的方法数

4.Sample Input

1 2 5 10 2


3 2 3 1 10


1000 2 2 2 900

5.Sample Output

4


27

6.HINT

7.Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP+容斥原理+思路~

先DP预处理出不限制使用次数的情况数,用f[i]表示i元的情况数,那么f[i]=sum{f[i-c[j]]},其中i>=c[j],f[0]=1。

f数组的更新要按照基本法硬币的种类数,防止情况重复。

然后,对于每次花费,答案为没有超过的种类数-超过1种的种类数+超过2种的种类数-超过3种的种类数+超过4种的种类数(这里均为“至少”),dfs一下即可,要注意sum<0的情况。

f数组和ans都要开long long!


#include
#include
using namespace std;
#define ll long long

int n,c[5],d[5],s;
ll ans,f[100001];

int read()
{
 int x=0,f=1;char ch=getchar();
 while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}
 while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
 return x*f;
}

void dfs(int u,int v,int sum)
{
 if(sum<0) return;
 if(u==5)
 {
  ans+=(ll)((v&1) ? -f[sum]:f[sum]);
  return;
 }
 dfs(u+1,v^1,sum-c[u]*(d[u]+1));dfs(u+1,v,sum);
}

int main()
{
 for(int i=1;i<=4;i++) c[i]=read();n=read();f[0]=1;
 for(int i=1;i<=4;i++)
   for(int j=1;j<=100000;j++) f[j]+=j>=c[i] ? f[j-c[i]]:0;
 while(n--)
 {
  for(int i=1;i<=4;i++) d[i]=read();s=read();
  ans=0;dfs(1,0,s);
  printf("%lld\n",ans);
 }
 return 0;
}





转载请注明:CodingBlog » BZOJ 1042 [HAOI2008] 硬币购物

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情