bzoj2287 [POJ Challeng]消失之物（01背包）

count[i][j]:
1. j>=v[i],count[i][j]=f[j]-count[i][j-v[i]]。
用能装满j的所有方案，减去用了第i个物品的方案(即不用第i个物品装满j-v[i]的所有方案)
2. j< v[i],count[i][j]=f[j].
j< v[i]，能装满j的所有方案一定都没有用第i个物品。
tips:取模的时候注意减成负数了的情况。。

#include 
#include 
#define N 2005
int n,m,v[N],f[N],c[N];
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
int main(){
//  freopen("a.in","r",stdin);n=read();m=read();for(int i=1;i<=n;++i) v[i]=read();f[0]=1;for(int i=1;i<=n;++i)for(int j=m;j>=v[i];--j)f[j]=(f[j]+f[j-v[i]])%10;for(int i=1;i<=n;++i){memset(c,0,sizeof(c));c[0]=1;for(int j=1;j<=m;++j)c[j]= j>=v[i]?f[j]-c[j-v[i]]:f[j],c[j]=(c[j]+10)%10;for(int j=1;j<=m;++j) printf("%d",c[j]);puts("");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！