luoguP4141
Description
Solution
没有丢失物品时,显然直接DP即可,用 $ f_i $ 表示 凑成 i 的答案
丢失物品i后,显然对于$ f_j $ 不能由 $f_{j-w_{i}} $ 转移
令 $ g_{i,j} $ 表示 不用 i时凑成j的答案,显然 $ g_{j} = f_{j} - g_{j - w_{i}} $
#include<bits/stdc++.h> using namespace std; inline int read() { int f = 1,x = 0; char ch; do { ch = getchar(); if(ch == '-') f = -1; }while(ch < '0'||ch > '9'); do { x = (x<<3) + (x<<1) + ch - '0'; ch = getchar(); }while(ch >= '0'&&ch <= '9'); return f*x; } const int MAXN = 2000 + 10; int n,m; int w[MAXN]; int f[MAXN],g[MAXN]; int main() { 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;j>=w[i];j--) { f[j] += f[j-w[i]]; f[j] %= 10; // cout << j << " " << f[j] <<endl; } } // for(int i=0;i<=m;i++) cout << f[i] << " "; // cout << endl; g[0] = 1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(j < w[i]) g[j] = f[j]; else g[j] = (f[j]-g[j-w[i]] +10)%10; printf("%d",g[j]); } printf(" "); } }