题目链接:https://www.luogu.org/problem/P1450
题目描述
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
分析:相信各位小伙伴和我一样,第一眼看这个题:这不是个多重背包的板子题吗??
But,看一下数据范围,这么暴力的做法根本行不通啊,T飞去了;
那有什么巧妙的方法来解决这道题呢?
如果说对于每个询问,没有硬币数量的限制,那就是个完全背包是吧,相信大家一定都能看出来的;
那么我们是不是可以想一想,拿这个完全背包减掉不符合限制的那一部分,是不是就是答案了呢?
这个还是比较好办的啊,不合法的方案就是(f[s−(d_j+1)*c_j])(j为第几种硬币),想一想为什么?
我先固定把这种硬币用上(d_j+1)个,这样得到的结果一定是不合法的,那么不合法的方案数自然就是:总和扣掉(d_j+1)个(c_j)硬币后的完全背包方法种数;
是不是非常巧妙?(没错我也是看了题解的)
所以最终答案就是(f[s]-sum_{j=1}^{4}f[s−(d_j+1)*c_j]);
所以要怎样求这个答案呢?这里还有一点点小问题:你使用硬币1的不合法方案与你使用硬币2的不合法方案有重叠,怎么解决?
容斥一下就好了;怎么容斥?详见代码.
注意事项:1.开long long!不开只有50分亲测;
2.预处理(f[0]=1)(凑齐0元只有一种方案:什么都不选),否则程序输出为0;
#include <bits/stdc++.h>
#define int long long
#define N (100000+5)
using namespace std;
int tot,ans,ss;
int c[5],d[5],dp[N];
void dfs(int k,int s,int p){//当前第k种硬币,剩余s元要凑,p为符号判断;
if(s<0) return;//凑够了(多了),return
if(k==5){//硬币种类已经选完
ans+=dp[s]*p;//ans加一下,容斥
return;
}
dfs(k+1,s,p);//符合限制的方案
dfs(k+1,s-(d[k]+1)*c[k],-p);//不符合限制的方案,注意变号
}
signed main(){
for(int i=1;i<=4;i++)scanf("%lld",&c[i]);
scanf("%lld",&tot);
dp[0]=1;
for(int i=1;i<=4;i++){
for(int j=c[i];j<=100000;j++){
dp[j]=dp[j]+dp[j-c[i]];
}
}//完全背包
for(int i=1;i<=tot;i++){
ans=0;
for(int j=1;j<=4;j++)scanf("%lld",&d[j]);
scanf("%lld",&ss);
dfs(1,ss,1);
printf("%lld
",ans);
}
return 0;
}
但愿大家能看懂吧......
反正我们机房的某些大佬写的博客实在是晦涩难懂,满篇幅的都是"......即可","显然......";
实在是跟不上dalao们的思维啊,看来我还要加油啊!