【题目链接】
【算法】
此题是一道好题！
首先，我们发现 : 付款方法数 = 不受限制的方法数 - 受限制的方法数
那么，我们怎么求呢？
我们用dp求出不受限制的方法数（f[i]表示买i元的东西，不受硬币限制，有多少种方案），只需用01背包的
方法就可以了，实现非常简单
那么受限制的方法数怎么求呢？由容斥原理可知，受限制的方法数 = 第一种硬币超限 + 第二种硬币超限 + ...
- 第一，二，三，四种硬币超限
第一种硬币超限，其实就是先选（d1 + 1)枚第一种硬币，其他随便选，那么对应的数量就是
f[s - (d1 + 1） * c[1]]，其他情况类似，注意当减下来小于零时是不可以的
于是，这道题便迎刃而解了！
【代码】
#include<bits/stdc++.h> using namespace std; #define MAXS 100010 long long i,j,d1,d2,d3,d4,T,s; long long c[5]; long long ans; long long f[MAXS]; int main() { scanf("%lld%lld%lld%lld%lld",&c[1],&c[2],&c[3],&c[4],&T); f[0] = 1; for (i = 1; i <= 4; i++) { for (j = c[i]; j < MAXS; j++) { f[j] += f[j-c[i]]; } } while (T--) { scanf("%lld%lld%lld%lld%lld",&d1,&d2,&d3,&d4,&s); ans = f[s]; if (s - (d1 + 1) * c[1] >= 0) ans -= f[s - (d1 + 1) * c[1]]; if (s - (d2 + 1) * c[2] >= 0) ans -= f[s - (d2 + 1) * c[2]]; if (s - (d3 + 1) * c[3] >= 0) ans -= f[s - (d3 + 1) * c[3]]; if (s - (d4 + 1) * c[4] >= 0) ans -= f[s - (d4 + 1) * c[4]]; if (s - (d1 + 1) * c[1] - (d2 + 1) * c[2] >= 0) ans += f[s - (d1 + 1) * c[1] - (d2 + 1) * c[2]]; if (s - (d1 + 1) * c[1] - (d3 + 1) * c[3] >= 0) ans += f[s - (d1 + 1) * c[1] - (d3 + 1) * c[3]]; if (s - (d1 + 1) * c[1] - (d4 + 1) * c[4] >= 0) ans += f[s - (d1 + 1) * c[1] - (d4 + 1) * c[4]]; if (s - (d2 + 1) * c[2] - (d3 + 1) * c[3] >= 0) ans += f[s - (d2 + 1) * c[2] - (d3 + 1) * c[3]]; if (s - (d2 + 1) * c[2] - (d4 + 1) * c[4] >= 0) ans += f[s - (d2 + 1) * c[2] - (d4 + 1) * c[4]]; if (s - (d3 + 1) * c[3] - (d4 + 1) * c[4] >= 0) ans += f[s - (d3 + 1) * c[3] - (d4 + 1) * c[4]]; if (s - (d1 + 1) * c[1] - (d2 + 1) * c[2] - (d3 + 1) * c[3] >= 0) ans -= f[s - (d1 + 1) * c[1] - (d2 + 1) * c[2] - (d3 + 1) * c[3]]; if (s - (d1 + 1) * c[1] - (d2 + 1) * c[2] - (d4 + 1) * c[4] >= 0) ans -= f[s - (d1 + 1) * c[1] - (d2 + 1) * c[2] - (d4 + 1) * c[4]]; if (s - (d1 + 1) * c[1] - (d3 + 1) * c[3] - (d4 + 1) * c[4] >= 0) ans -= f[s - (d1 + 1) * c[1] - (d3 + 1) * c[3] - (d4 + 1) * c[4]]; if (s - (d2 + 1) * c[2] - (d3 + 1) * c[3] - (d4 + 1) * c[4] >= 0) ans -= f[s - (d2 + 1) * c[2] - (d3 + 1) * c[3] - (d4 + 1) * c[4]]; if (s - (d1 + 1) * c[1] - (d2 + 1) * c[2] - (d3 + 1) * c[3] - (d4 + 1) * c[4] >= 0) ans += f[s - (d1 + 1) * c[1] - (d2 + 1) * c[2] - (d3 + 1) * c[3] - (d4 + 1) * c[4]]; printf("%lld ",ans); } return 0; }