题意：

给出n，m，求用除了第i（1≤i≤n）个之外的物品填满容量为j（1≤j≤m）的背包的方法数。n，m≤2000。

题解：

令f[n][j]为所有物品可用填满j的方案数，F[i][j]为题目所求，则当j<a[i]时F[i][j]=f[n][j]，否则F[i][j]=f[n][j]-F[i][j-a[i]]。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 2001 6 using namespace std; 7  8 inline int read(){ 9     char ch=getchar(); int f=1,x=0;10     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}11     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();12     return f*x;13 }14 int f[maxn],c[maxn][maxn],n,m,a[maxn];15 int main(){16     n=read(); m=read(); inc(i,1,n)a[i]=read(); f[0]=1;17     inc(i,1,n)for(int j=m;j>=a[i];j--)f[j]=(f[j]+f[j-a[i]])%10;18     inc(i,1,n){19         c[i][0]=1;20         inc(j,1,m){
   if(j
       
      
     

 

20160905