贪心 + Dp
Part1
看上去很像背包，但是发现最后答案和堆放的顺序有关，很容易想到状压，但是复杂度不允许。
而且发现如果一个一个向上放，当前决策会有后效性，题目也不允许在开一维状态。
Part2
对于后效性，我们可以每次把箱子放在最下面，就没有后效性了。
重点是解决顺序问题，考虑两个箱子 \(i ,j\) 在什么情况下，其中一种会优先放在下面。我们想让在这个箱子上面放的重量尽量多，那么有 \(s_i-w_j \geqslant s_j-w_i\) ，那么 \(s_i+w_i \geqslant s_j+w_j\) , 那我们按照 \(s+w\) 从小到大（越大的越放在下面）排序即可。
Part3
剩下的就是普通 \(0/1\)背包, 设 \(dp_i\) 表示当前重量为 \(i\) 的最大价值，那么有：
\[dp_{j+w_i}=\max(dp_{j+w_i} , dp_j+v_i) \]复杂度 \(\Theta(n^2)\)
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
const int N=1e3+10;
const int M=2e4+10;
using namespace std;
inline int read() {
int f=1, x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return f*x;
}
inline void write(int x) {
cout<<x; putchar('\n');
}
int n;
struct node {
int w, s, v;
}a[N];
inline bool cmp(node x,node y) {
return x.w+x.s < y.w+y.s;
}
int dp[M];
signed main() {
n=read();
for(int i=1;i<=n;i++) {
a[i]=(node){read(), read(), read()};
}
sort(a+1, a+n+1, cmp);
int ans=0;
for(int i=1;i<=n;i++) {
for(int j=a[i].s;j>=0;j--) {
dp[j+a[i].w]=max(dp[j+a[i].w], dp[j]+a[i].v);
ans=max(ans, dp[j+a[i].w]);
}
}
write(ans);
return 0;
}