Luogu P4095 [HEOI2013]Eden 的新背包問題

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
int n, v[B], w[B], p[B], f[B][B], g[B][B], a, b, q;

int main(int argc, char const *argv[]) {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i] >> p[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 1000; j++) f[i][j] = f[i - 1][j];
    int num = p[i];
    for (int k = 1; num; k <<= 1) {
      if (k > num) k = num;
      num -= k;
      for (int j = 1000; j >= w[i] * k; j--)
        f[i][j] = max(f[i][j], f[i][j - w[i] * k] + v[i] * k);
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = 1; j <= 1000; j++) g[i][j] = g[i + 1][j];
    int num = p[i];
    for (int k = 1; num; k <<= 1) {
      if (k > num) k = num;
      num -= k;
      for (int j = 1000; j >= w[i] * k; j--)
        g[i][j] = max(g[i][j], g[i][j - w[i] * k] + v[i] * k);
    }
  }
  cin >> q;
  while (q--) {
    cin >> a >> b; int ans = 0;
    for (int i = 0; i <= b; i++) ans = max(ans, f[a][i] + g[a + 2][b - i]);
    cout << ans << endl;
  }
}