首页 > 代码库 > 【BZOJ 1042】 [HAOI2008]硬币购物
【BZOJ 1042】 [HAOI2008]硬币购物
1042: [HAOI2008]硬币购物
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1175 Solved: 697
[Submit][Status]
Description
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
Input
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s
Output
每次的方法数
Sample Input
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
3 2 3 1 10
1000 2 2 2 900
Sample Output
4
27
27
HINT
数据规模
di,s<=100000
tot<=1000
dp+容斥原理。
首先可以预处理f[i]表示在四种硬币没有限制的情况下买i的东西有几种付款方式。f[i]=sigma(f[i-c[k]]) (1<=k<=4)
一定要注意：一种硬币算完再算第二种！！！
即for (int i=1;i<=4;i++) for (int j=1;j<=maxcost;j++)！！
因为反过来就会有重复！！！
接下来就可以容斥了：
得到面值S的超过限制的方案数 - 第1种硬币超过限制的方案数 - 第2种硬币超过限制的方案数 - 第3种硬币超过限制的方案数 - 第4种硬币超过限制的方案数 + 第1,2种硬币同时超过限制的方案数 + 第1,3种硬币同时超过限制的方案数 + ...... + 第1,2,3,4种硬币全部同时超过限制的方案数。
（from byvoid）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#define M 100005
#define LL long long
using namespace std;
LL f[M],ans;
int d[5],c[5],t,s;
LL F(int x)
{
return x>=0?f[x]:0LL;
}
void RC()
{
for (int i=1;i<=4;i++)
ans-=F(s-c[i]*(d[i]+1));
for (int i=1;i<=4;i++)
for (int j=i+1;j<=4;j++)
ans+=F(s-c[i]*(d[i]+1)-c[j]*(d[j]+1));
int now;
for (int i=1;i<=4;i++)
{
now=0;
for (int j=1;j<=4;j++)
if (j!=i) now+=c[j]*(d[j]+1);
ans-=F(s-now);
}
ans+=F(s-now-c[4]*(d[4]+1));
}
int main()
{
scanf("%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&t);
f[0]=1;
for (int j=1;j<=4;j++)
for (int i=1;i<=100000;i++)
if (i>=c[j]) f[i]+=f[i-c[j]];
while (t--)
{
for (int i=1;i<=4;i++)
scanf("%d",&d[i]);
scanf("%d",&s);
ans=f[s];
RC();
printf("%lld\n",ans);
}
return 0;
}
感悟：
1.因为只有四种面值的硬币，所以容斥非常好算
2.一定要注意dp的循环嵌套，防止重复！！
3.byvoid题解
【BZOJ 1042】 [HAOI2008]硬币购物
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。