硬币购物
[HAOI2008]硬币购物
https://ac.nowcoder.com/acm/problem/19974
分析
我的心理反应：要是没有个数限制多好啊QwQ
于是：我们先处理出一个完全背包，求出每一种容量拼凑的方案数。这时，如果要求s，那么肯定会有用超过个数的
那么这时不可取的，就得减去这些超过个数的不合法方案。根据容斥原理，我们在减去1,2,3,4超限制的同时，多减
了一部分，还要在加回来，然后又多加了一部分，还得重新减。。。。。。然后就能得出答案
代码
/* 容斥+背包 */ #include<bits/stdc++.h> #define N 100005 #define ll long long using namespace std; ll tot,s; ll price[6],num[6],dp[N]; inline ll f(int id) { return price[id]*(num[id]+1); } int main() { for (int i=1;i<=4;i++) scanf("%lld",&price[i]); scanf("%lld",&tot); dp[0]=1; for (int i=1;i<=4;i++) for (int j=price[i];j<=100000;j++) dp[j]+=dp[j-price[i]]; while(tot--) { for (int i=1;i<=4;i++) scanf("%lld",&num[i]); scanf("%lld",&s); ll ans=dp[s]; if(s>=f(1)) ans-=dp[s-f(1)]; if(s>=f(2)) ans-=dp[s-f(2)]; if(s>=f(3)) ans-=dp[s-f(3)]; if(s>=f(4)) ans-=dp[s-f(4)]; if(s>=f(1)+f(2)) ans+=dp[s-f(1)-f(2)]; if(s>=f(1)+f(3)) ans+=dp[s-f(1)-f(3)]; if(s>=f(1)+f(4)) ans+=dp[s-f(1)-f(4)]; if(s>=f(2)+f(3)) ans+=dp[s-f(3)-f(2)]; if(s>=f(4)+f(2)) ans+=dp[s-f(4)-f(2)]; if(s>=f(3)+f(4)) ans+=dp[s-f(3)-f(4)]; if(s>=f(1)+f(2)+f(3)) ans-=dp[s-f(1)-f(2)-f(3)]; if(s>=f(1)+f(2)+f(4)) ans-=dp[s-f(1)-f(2)-f(4)]; if(s>=f(4)+f(2)+f(3)) ans-=dp[s-f(4)-f(2)-f(3)]; if(s>=f(1)+f(4)+f(3)) ans-=dp[s-f(1)-f(4)-f(3)]; if(s>=f(1)+f(2)+f(3)+f(4)) ans+=dp[s-f(1)-f(2)-f(3)-f(4)]; printf("%lld\n",ans); } return 0; }
每日一题 文章被收录于专栏
每天的题，为了牛币
投递美团等公司10个岗位
基恩士成长空间 421人发布