Knight defeats demon king (Backpack & DP)

The knight defeated the demon king ( knapsack &dp)

Because the plan is different , It depends on the energy and difference used by a knight .

Therefore, we consider using backpacks to deal with the energy used by each Knight $i$ The biggest damage , When seeking the maximum, in order to include all cases .

Then proceed dp, Make $f(i,j)$ Before presentation $i$ Knights caused $j$ Number of schemes for point damage .

Specially ,$f(i,m)$ Before presentation $i$ Knights cause greater than or equal to $j$ Number of schemes for point damage .

Then proceed dp that will do .

Time complexity ：$O(n\times 3000)$

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int mod = 998244353;

int n, m;

int fans[3009][3009], ff[3009];
int a[3009], b[3009];
void solved() {
    
    cin >> n >> m;
    fans[0][0] = 1;
    int s;
    for(int ttf = 1; ttf <= n; ttf ++) {
    
        cin >> s;
        for(int i = 0; i < s; i ++) cin >> a[i];
        for(int i = 0; i < s; i ++) cin >> b[i];
        for(int i = 0; i <= 3000; i ++) ff[i] = 0;  ///  initialization  dp  Array 
        for(int i = 0; i < s; i ++) {
      ///  Find out the maximum attack power that each energy consumption of the current knight can cause 
            for(int j = 3000; j >= b[i]; j --) {
    
                if(ff[j - b[i]] || j - b[i] == 0)
                    ff[j] = max(ff[j - b[i]] + a[i], ff[j]);
            }
        }  /// n Total time complexity of knights ： sum(s) * 3000
        for(int i = 0; i <= 3000; i ++) {
    
            if(ff[i] == 0 && i != 0) continue;  ///  Some values cannot be represented , The magnitude of the value that can be represented is  sum(b)
            if(ff[i] > m) ff[i] = m;  ///  Attack overflow processing 
            for(int j = 0; j < ff[i]; j ++)  ///  Here is the number of schemes in the attack overflow part , It needs to be calculated separately 
                fans[ttf][m] = (fans[ttf][m] + fans[ttf - 1][m - j]) % mod;
            for(int j = m; j >= ff[i]; j --)  ///  This  for  And the one above  for  The total time complexity of is ： sum(b) * m
                fans[ttf][j] = (fans[ttf][j] + fans[ttf - 1][j - ff[i]]) % mod;
        }  /// n The total time complexity of a knight here ： n * 3000
    }  ///  Total time complexity ： sum(s) * 3000 + n * 3000 + sum(b) * m
    cout << fans[n][m];
}
int main() {
    
    // int ttx; cin >> ttx; while(ttx --) 
        solved();
    return 0;
}