#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010, M = 20010;
int f[N][M], n, m;
int v, w, s;
int main() {
cin >> n >> m;
int res = 0;
for (int i = 1; i <= n; i++) {
cin >> v >> w >> s;
for (int j = 0; j <= m; j++) {
f[i][j] = f[i-1][j];
for (int l = 0; l <= s; l++) {
if (j < l * v) continue;
f[i][j] = max(f[i][j], f[i-1][j - l*v] + l * w);
res = max(res, f[i][j]);
}
}
}
cout << res <<endl;
}
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20100;
int f[N], g[N], n, m;
int v, w, s;
int main() {
cin >> n >> m;
int res = 0;
// cout << 22 <<endl;
for (int i = 1; i <= n; i++) {
cin >> v >> w >> s;
memcpy(g, f, sizeof f);
for (int j = 0; j <= m; j++) {
f[j] = g[j];
for (int l = 0; l <= s; l++) {
if (j < l * v) continue;
f[j] = max(f[j], g[j - l*v] + l * w);
res = max(res, f[j]);
}
}
}
cout << res <<endl;
}
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20100;
int f[N], g[N], n, m, q[N];
int v, w, s;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v >> w >> s;
memcpy(g, f, sizeof f);
for (int j = 0; j <v; j++) {
int hh = 0, tt = -1;
for (int k = j; k <= m; k+= v) {
if (hh <= tt && q[hh] + s * v < k) hh++;
if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k-q[hh])/v*w);
while(hh <= tt && g[q[tt]] - q[tt]/v*w <= g[k] - k/v*w) tt--;
q[++tt] = k;
}
}
}
cout << f[m] <<endl;
}
参考文献
C++ 代码
blablabla