烛光晚餐
题目
-> 传送门 <-
题解
因为下标有可能越界，所以我们平移一下，然后就变成了一道二维背包题。
code
#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iOStream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define fup(i, a, b) for(int i = a; i <= b; ++i)
#define fdown(i, a, b) for(int i = a; i >= b; --i)
#define pri_(k) printf("%d ", k)
#define pri(k) printf("----%d---\n", k)
const int maxn = 150;
const int inf = 0x3f3f3f3f;
typedef long long ull;
namespace millope {
inline void kswap(int &a, int &b) { a ^= b ^= a ^= b; }
inline int kmin(int a, int b) { return a > b ? b : a; }
inline int kmax(int a, int b) { return a > b ? a : b; }
inline int read() {
int s = 0, w = 1;
char ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
return s * w;
}
}
using namespace millope;
using namespace std;
int n;
int v;
int ans;
int c[maxn];
int x[maxn];
int y[maxn];
int f[510][1050];
const int tran = 1000;
int main() {
ans = -1;
memset(f, 0xcf, sizeof(f));
n = read(), v = read();
for (int i = 1; i <= n; ++i) {
c[i] = read();
x[i] = read();
y[i] = read();
}
for (int i = v; i >= 0; i--) {
f[i][tran >> 1] = 0;
}
for (int i = 1; i <= n; ++i) {
for (int j = v; j >= c[i]; --j) {
if (x[i] > 0) {
for (int k = tran; k >= x[i]; --k) {
f[j][k] = kmax(f[j][k], f[j - c[i]][k - x[i]] + y[i]);
}
}
else {
for (int k = 0; k <= x[i] + tran; ++k) {
f[j][k] = kmax(f[j][k], f[j - c[i]][k - x[i]] + y[i]);
}
}
}
}
for (int i = v; i >= 0; --i) {
for (int j = (tran >> 1); j <= tran; ++j) {
ans = kmax(ans, f[i][j]);
}
}
printf("%d\n", ans);
return 0;
}