[HAOI2008]硬币购物

Time Limit:10000MS Memory Limit:165536K
Total Submit:11 Accepted:8
Case Time Limit:1000MS

Description

硬币购物
一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。
每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

Input

第一行
c1,c2,c3,c4,tot
下面tot行
d1,d2,d3,d4,s

Output

每次的方法数

Sample Input

Sample Output

Source
这题有点NB的，DP+容斥原理囧。。
Code:

#include<iostream>using namespace std;const int maxn=4,maxs=100000+1;typedef long long ll;ll Dp[maxs]={0};int C[maxn];void Cal(){ Dp[0]=1; for(int i=0;i<maxn;i++) for(int j=C[i];j<maxs;j++) Dp[j]+=Dp[j-C[i]];}int D[maxn];void dfs(int p,int ch,int now,ll&ret){ if(now<0) return; if(p==maxn) { if(ch&1) ret-=Dp[now]; else ret+=Dp[now]; return; } dfs(p+1,ch+1,now-C[p]*(D[p]+1),ret); dfs(p+1,ch,now,ret);}void solve(){ int s;ll ans=0;for(int i=0;i<maxn;i++)cin>>D[i]; cin>>s; dfs(0,0,s,ans); cout<<ans<<endl;}int main(){ //freopen("in","r",stdin); int t; for(int i=0;i<maxn;i++)cin>>C[i];cin>>t; Cal(); while(t–)solve();}427数据规模di,s<=100000tot<=10001 2 5 10 23 2 3 1 101000 2 2 2 900