[HAOI2008]硬币购物题解

本文主要是介绍[HAOI2008]硬币购物题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

分析

一道容斥好题，如果用多重背包，估计会t死的，我们可先做完全背包，求出方案数，再用总方案数减去不可用的方案数（比如说对于每个硬币i，硬币数超过c[i]的），这时你会发现可以用容斥做，手动容斥即可，时间：3500ms。
上代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll c[5],l[5],s,cnt,f[100010],ans;
int main(){for(int i=1;i<=4;i++)scanf("%lld",&c[i]);scanf("%lld",&cnt);while(cnt--){for(int i=1;i<=4;i++)scanf("%lld",&l[i]);scanf("%lld",&s);memset(f,0,sizeof(f));f[0]=1;for(int i=1;i<=4;i++)for(int j=c[i];j<=s;j++)f[j]+=f[j-c[i]];       ans=f[s];for(int i=1;i<=4;i++)   if(s-c[i]*(l[i]+1)>=0)ans-=f[s-c[i]*(l[i]+1)];if(s-(c[1]*(l[1]+1))-(c[2]*(l[2]+1))>=0)ans+=f[s-(c[1]*(l[1]+1))-(c[2]*(l[2]+1))];if(s-(c[2]*(l[2]+1))-(c[3]*(l[3]+1))>=0)ans+=f[s-(c[2]*(l[2]+1))-(c[3]*(l[3]+1))];if(s-(c[3]*(l[3]+1))-(c[4]*(l[4]+1))>=0)ans+=f[s-(c[3]*(l[3]+1))-(c[4]*(l[4]+1))];if(s-(c[2]*(l[2]+1))-(c[4]*(l[4]+1))>=0)ans+=f[s-(c[2]*(l[2]+1))-(c[4]*(l[4]+1))];if(s-(c[1]*(l[1]+1))-(c[3]*(l[3]+1))>=0)ans+=f[s-(c[1]*(l[1]+1))-(c[3]*(l[3]+1))];if(s-(c[1]*(l[1]+1))-(c[4]*(l[4]+1))>=0)ans+=f[s-(c[1]*(l[1]+1))-(c[4]*(l[4]+1))];if((s-(c[1]*(l[1]+1))-(c[2]* l[2]+1))-(c[3]*(l[3]+1))>=0)ans-=f[s-(c[1]*(l[1]+1))-(c[2]*(l[2]+1))-(c[3]*(l[3]+1))];if(s-(c[2]*(l[2]+1))-(c[3]*(l[3]+1))-(c[4]*(l[4]+1))>=0)ans-=f[s-(c[2]*(l[2]+1))-(c[3]*(l[3]+1))-(c[4]*(l[4]+1))];if(s-(c[1]*(l[1]+1))-(c[3]*(l[3]+1))-(c[4]*(l[4]+1))>=0)ans-=f[s-(c[1]*(l[1]+1))-(c[3]*(l[3]+1))-(c[4]*(l[4]+1))];if(s-(c[1]*(l[1]+1))-(c[2]*(l[2]+1))-(c[4]*(l[4]+1))>=0) ans-=f[s-(c[1]*(l[1]+1))-(c[2]*(l[2]+1))-(c[4]*(l[4]+1))];if(s-(c[1]*(l[1]+1))-(c[2]*(l[2]+1))-(c[3]*(l[3]+1))-(c[4]*(l[4]+1))>=0)ans+=f[s-(c[1]*(l[1]+1))-(c[2]*(l[2]+1))-(c[3]*(l[3]+1))-(c[4]*(l[4]+1))];printf("%lld\n",ans);}return 0;
}