长春网站建长春做网站,建设网站经验,企业域名注册流程,公司注册网上核名app【BZOJ1042】硬币购物#xff08;动态规划#xff0c;容斥原理#xff09; 题面 BZOJ Description 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西#xff0c;去了tot次。每次带di枚ci硬币#xff0c;买s i的价值的东西。请问每次有多少种付款方法。 In…【BZOJ1042】硬币购物动态规划容斥原理 题面 BZOJ Description 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西去了tot次。每次带di枚ci硬币买s i的价值的东西。请问每次有多少种付款方法。 Input 第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s100000,tot1000 Output 每次的方法数 Sample Input 1 2 5 10 2 3 2 3 1 10 1000 2 2 2 900 Sample Output 4 27 题解 真题真好啊。 先不考虑任何有关于硬币个数的限制 设\(f[i]\)表示没有任何限制的情况下价格为\(n\)的方案数 直接做一个背包就行了。 现在加上限制来看我们用总方案减去不合法。 总方案是\(f[n]\)不合法呢 某一个硬币如果不合法那么它就要用\(d1\)个 剩下的随便选也就是\(f[n-c*(d1)]\) 这样直接容斥计算即可。 #includecstdio
#includecstdlib
#includecstring
#includecmath
#includealgorithm
#includeset
#includemap
#includevector
#includequeue
using namespace std;
#define ll long long
#define RG register
inline int read()
{RG int x0,t1;RG char chgetchar();while((ch0||ch9)ch!-)chgetchar();if(ch-)t-1,chgetchar();while(ch9ch0)xx*10ch-48,chgetchar();return x*t;
}
int c[4],d[4],S;
ll f[111111];
int main()
{for(int i0;i4;i)c[i]read();f[0]1;for(int k0;k4;k)for(int jc[k];j100000;j)f[j]f[j-c[k]];int Qread();while(Q--){for(int i0;i4;i)d[i]read();Sread();ll ss,ans0;for(int i0,tt;i16;i){sstt0;for(int j0;j4;j)if(i(1j))tt,ss(d[j]1)*c[j];if(ssS)continue;(tt1)?ans-f[S-ss]:ansf[S-ss];}printf(%lld\n,ans);}return 0;
}转载于:https://www.cnblogs.com/cjyyb/p/8656700.html
