首页 > 代码库 > BZOJ 1042 硬币购物
BZOJ 1042 硬币购物
先不考虑限制,那么有dp[i]表示i元钱的方案数。
然后考虑限制,发现可以容斥。
其实整个题就是两个容斥原理。感觉出的蛮好的。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100500 using namespace std; long long f[maxn],c[5],d[5],n,s,ans; void pre_dp() { f[0]=1; for (long long i=1;i<=maxn-500;i++) { for (long long j=1;j<=4;j++) if (i>=c[j]) f[i]+=f[i-c[j]]; for (long long j=1;j<=4;j++) for (long long k=j+1;k<=4;k++) if (i>=c[j]+c[k]) f[i]-=f[i-c[j]-c[k]]; for (long long j=1;j<=4;j++) for (long long k=j+1;k<=4;k++) for (long long l=k+1;l<=4;l++) if (i>=c[j]+c[k]+c[l]) f[i]+=f[i-c[j]-c[k]-c[l]]; if (i>=c[1]+c[2]+c[3]+c[4]) f[i]-=f[i-c[1]-c[2]-c[3]-c[4]]; } } void work() { ans=0;ans+=f[s]; for (long long i=1;i<=4;i++) if (s>=d[i]*c[i]) ans-=f[s-d[i]*c[i]]; for (long long i=1;i<=4;i++) for (long long j=i+1;j<=4;j++) if (s>=d[i]*c[i]+d[j]*c[j]) ans+=f[s-d[i]*c[i]-d[j]*c[j]]; for (long long i=1;i<=4;i++) for (long long j=i+1;j<=4;j++) for (long long k=j+1;k<=4;k++) if (s>=d[i]*c[i]+d[j]*c[j]+d[k]*c[k]) ans-=f[s-d[i]*c[i]-d[j]*c[j]-d[k]*c[k]]; if (s>=d[1]*c[1]+d[2]*c[2]+d[3]*c[3]+d[4]*c[4]) ans+=f[s-(d[1]*c[1]+d[2]*c[2]+d[3]*c[3]+d[4]*c[4])]; printf("%lld\n",ans); } int main() { for (long long i=1;i<=4;i++) scanf("%lld",&c[i]); scanf("%lld",&n); pre_dp(); for (long long i=1;i<=n;i++) { for (long long j=1;j<=4;j++) {scanf("%lld",&d[j]);d[j]++;} scanf("%lld",&s); work(); } return 0; }
BZOJ 1042 硬币购物
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。