BZOJ.2287.[POJ Challenge]消失之物(退背包)

时间:2022-03-14 08:38:50

BZOJ

洛谷

退背包。和原DP的递推一样,再减去一次递推就行了。

f[i][j] = f[i-1][j-w[i]] + f[i-1][j]
f[i-1][j] = f[i][j] - f[i-1][j-w[i]]
//1136kb	56ms
#include <cstdio>
#include <cctype>
#include <cstring>
#define gc() getchar()
const int N=2005; int w[N],f[N],g[N]; inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
} int main()
{
int n=read(),m=read();
for(int i=1; i<=n; ++i) w[i]=read();
f[0]=1;
for(int i=1; i<=n; ++i)
for(int j=m,wi=w[i]; j>=wi; --j) (f[j]+=f[j-wi])%=10;
for(int i=1; i<=n; ++i)
{
memcpy(g,f,sizeof g);
for(int wi=w[i],j=wi; j<=m; ++j) (g[j]+=10-g[j-wi])%=10;//g[j]-=g[j-wi]
for(int j=1; j<=m; ++j) putchar(g[j]+'0');
putchar('\n');
} return 0;
}