bzoj2287:[POJ Challenge]消失之物

思路:首先先背包预处理出f[x]表示所有物品背出体积为x的方案数。然后统计答案,利用dp。

C[i][j]表示不用物品i,组成体积j的方案数。

转移公式:C[i][j]=f[j]-C[i][j-w[i]]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 2005 int n,m;
int f[maxn],w[maxn],ans[maxn]; int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&w[i]);f[0]=1;
for (int i=1;i<=n;i++)
for (int j=m;j>=w[i];j--)
f[j]+=f[j-w[i]],f[j]%=10;
for (int i=1;i<=n;i++){
memset(ans,0,sizeof(ans)),ans[0]=1;
for (int j=1;j<=m;j++){
if (j>=w[i]) ans[j]=((f[j]-ans[j-w[i]])%10+10)%10;
else ans[j]=f[j];
printf("%d",ans[j]);
}
puts("");
}
return 0;
}
上一篇:kendo ui 富文本编辑控件 Editor 实现本地上传图片,并显示


下一篇:[bzoj2287][poj Challenge]消失之物_背包dp_容斥原理