2016-06-20

完全背包DP(做的时候都忘记自己当初怎么学得了  囧。。)，题目非同寻常的地方是n很小，价值固定，但有多组测试数据，我们首先想到将之按完全背包预处理出来，每一组时再减去不合法的，

减去不合法的可以用容斥原理，第一个不合法的方案数就是让第一个先取d1+1个其余随便取   f[s-(d1+1)*c1],那就减去1,2,3,4加上12,13,14,23,24,34减去123,124,134，234加上1234。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #define M 100008 8 #define ll long long 9 #define Mo 1234567810 using namespace std;11 ll read()12 {13 char ch=getchar();14 ll x=0,f=1;15 for(;ch<'0'||ch>'9';ch=getchar())16 if(ch=='-')17 f=-1;18 for(;ch>='0'&&ch<='9';ch=getchar())19 x=x*10+ch-'0';20 return x*f;21 }22 int c[5],n,m,a[5],b[5];23 ll f[M];24 int main()25 {26 f[0]=1;27 for(int i=1;i<=4;i++)28 c[i]=read();29 n=read();30 for(int i=1;i<=4;i++)31 for(int j=c[i];j<=100000;j++)32 f[j]+=f[j-c[i]];33 for(int i=1;i<=n;i++)34 {35 for(int j=1;j<=4;j++)36 a[j]=read();37 m=read();38 ll an=f[m];39 for(int j=1;j<=4;j++)40 if(m-(a[j]+1)*c[j]>=0)41 an-=f[m-(a[j]+1)*c[j]];42 for(int j=1;j<=4;j++)43 for(int k=j+1;k<=4;k++)44 if(m-(a[j]+1)*c[j]-(a[k]+1)*c[k]>=0)45 an+=f[m-(a[j]+1)*c[j]-(a[k]+1)*c[k]];46 for(int j=1;j<=4;j++)47 for(int k=j+1;k<=4;k++)48 for(int l=k+1;l<=4;l++)49 if(m-(a[l]+1)*c[l]-(a[j]+1)*c[j]-(a[k]+1)*c[k]>=0)50 an-=f[m-(a[l]+1)*c[l]-(a[j]+1)*c[j]-(a[k]+1)*c[k]];51 if(m-(a[1]+1)*c[1]-(a[2]+1)*c[2]-(a[3]+1)*c[3]-(a[4]+1)*c[4]>=0)52 an+=f[m-(a[1]+1)*c[1]-(a[2]+1)*c[2]-(a[3]+1)*c[3]-(a[4]+1)*c[4]];53 printf("%lld\n",an);54 }55 return 0;56 }