思路： 先處理出來f[j]表示這i個物品都可用 填滿容量j的方案數
容斥一發
處理出來g[j]=g[j-w[i]] 表示i不能用的時候 填滿容量j的方案數
//By SiriusRen#include <cstdio>using namespace std;int n,m,w[2005],f[2005],g[2005];int main(){ scanf("%d%d",&n,&m),f[0]=1; for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) f[j]=(f[j]+f[j-w[i]])%10; for(int i=1;i<=n;i++){ for(int j=0;j<w[i];j++)g[j]=f[j]; for(int j=w[i];j<=m;j++)g[j]=((f[j]-g[j-w[i]])%10+10)%10; for(int j=1;j<=m;j++)
新聞熱點
疑難解答
