洛谷p4141 前后两遍法
同Eden的新背包
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n, m; #define N 2010 #define M 2010 int v[N]; int f[N][M]; int g[N][M]; int Count(int i, int x) { int val = 0; for (int y = 0; y <= x; y++) { val += ((f[i - 1][y]%10)* (g[i + 1][x - y])%10); val%=10; } return val % 10; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> v[i]; } g[n+1][0] = 1; f[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { f[i][j] = f[i-1][j]; if(j>=v[i]) f[i][j] += f[i - 1][j - v[i]]; f[i][j] %= 10; } } for(int i = n;i;i--){ for(int j = 0;j<=m;j++){ g[i][j] = g[i+1][j]; if(j>=v[i]) g[i][j] += g[i+1][j-v[i]]; g[i][j] %= 10; } } for(int i = 1;i<=n;i++){ for(int j=1;j<=m;j++){ cout<<Count(i,j); } cout<<endl; } return 0; }```