BZOJ 1042 HAOI 2008 硬幣購物 容斥原理

BZOJ 1042 HAOI 2008 硬幣購物 容斥原理

題目大意：給出4個硬幣的價值和個數限制，求有多少種方法湊成S塊錢。

思路：很巧妙的一種想法，用到了4這個非常小的數字。我們可以先不管每個硬幣的個數限制，然後跑一次完全背包。之後把不符合的情況去除就行了。方法是，先減去一種硬幣超限的數目，然後加上兩種硬幣超限的數目，然後減去三種硬幣超限的數目，然後加上四種硬幣超限的個數。當然代碼就很丑了。。

CODE：

#include 
#include 
#include 
#include 
#define MAX 100010
#define P(i) (c[i] * (l[i] + 1))
using namespace std;
 
int c[5],l[5],s;
int cnt;
long long f[MAX],ans;
 
int main()
{
    for(int i = 1; i <= 4; ++i)  
        scanf("%d",&c[i]);
    cin >> cnt;
    for(int i = 1; i <= cnt; ++i) {
        for(int j = 1; j <= 4; ++j)
            scanf("%d",&l[j]);
        scanf("%d",&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 - P(_i) >= 0)
                ans -= f[s - P(_i)];
        if(s - P(1) - P(2) >= 0) ans += f[s - P(1) - P(2)];
        if(s - P(2) - P(3) >= 0) ans += f[s - P(2) - P(3)];
        if(s - P(3) - P(4) >= 0) ans += f[s - P(3) - P(4)];
        if(s - P(2) - P(4) >= 0) ans += f[s - P(2) - P(4)];
        if(s - P(1) - P(3) >= 0) ans += f[s - P(1) - P(3)];
        if(s - P(1) - P(4) >= 0) ans += f[s - P(1) - P(4)];
        if(s - P(1) - P(2) - P(3) >= 0)  ans -= f[s - P(1) - P(2) - P(3)];
        if(s - P(2) - P(3) - P(4) >= 0)  ans -= f[s - P(2) - P(3) - P(4)];
        if(s - P(1) - P(3) - P(4) >= 0)  ans -= f[s - P(1) - P(3) - P(4)];
        if(s - P(1) - P(2) - P(4) >= 0)  ans -= f[s - P(1) - P(2) - P(4)];
        if(s - P(1) - P(2) - P(3) - P(4) >= 0)   ans += f[s - P(1) - P(2) - P(3) - P(4)];
        printf("%lld\n",ans);
    }
    return 0;
}