是不是贪心就是sort一下
by WxjzKK @ 2020-07-05 21:55:16
这不就是个变了形的01背包吗
by _5011_ @ 2020-07-05 21:56:03
01背包内层循环是倒着循环到p[i]，改成这样之后倒着循环到max(p[i],q[i])不就好了
by _5011_ @ 2020-07-05 21:56:50
是的呀，可是太`蒻`的我怎么也搞不懂呀【可怜】
by WxjzKK @ 2020-07-05 21:56:59
@[WxjzKK](/user/160150) 考虑 01 背包的状态转移方程：
$dp_j=\max\{dp_j,dp_{j-p_i}+v_i\}$
要满足的是必须有 $p_i$ 才能花费掉 $p_i$。
然而现在条件变成了必须有 $q_i$ 才能花费掉 $p_i$，所以只需要修改那里就可以了
by _5011_ @ 2020-07-05 21:59:37
我搞懂了谢谢**大佬**
@[Zephyr_](/user/91127)
by WxjzKK @ 2020-07-05 21:59:49
谢谢大佬万岁
by WxjzKK @ 2020-07-05 22:00:32
@[Zephyr_](/user/91127)
大佬：
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<string>
#include<stack>
#include<queue>
using namespace std;
int p[501],q[501],v[501],dp[5001];
int main()
{
int n,m;
cin>>n>>m;
for (int i=1;i<=n;++i) cin>>p[i]>>q[i]>>v[i];
for (int i=1;i<=n;++i)
for (int j=m;j>=max(p[i],q[i]);--j)
dp[j]=max(dp[j],dp[j-p[i]]+v[i]);
cout<<dp[m]<<endl;
return 0;
}
```
碰到
```cpp
3 10
5 10 5
3 5 6
2 7 3
```
这组数据的输出是9，但实际答案确实11呀
by WxjzKK @ 2020-07-05 22:21:45
@[WxjzKK](/user/160150) 谢罪……
1. 因为是剩余空间必须超过 q[i]，而背包中转移的通常是使用的空间，所以我的那个方法其实是错的2333……
2. 所以 q[i] 要变为 m-q[i]，占用空间的范围也要变为区间 $[p[i],p[i]+q[i]]$。
3. 因为这个方程是严格从 0 开始转移，所以最后要对所有位置的 dp 值取 max。
4. 完整代码，你可以参考一下：（至少样例可过）
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<string>
#include<stack>
#include<queue>
using namespace std;
int p[501],q[501],v[501],dp[5001];
int main()
{
int n,m;
cin>>n>>m;
for (int i=1;i<=n;++i) cin>>p[i]>>q[i]>>v[i];
for (int i = 1;i <= n;i++) q[i] = m - q[i];
for (int i=1;i<=n;++i)
for (int j=min(q[i] + p[i], m);j>=p[i];--j)
dp[j]=max(dp[j],dp[j-p[i]]+v[i]);
int ans = 0;
for (int i = 1;i <= m;i++) ans = max(ans, dp[i]);
cout << ans;
return 0;
}
```
by _5011_ @ 2020-07-05 22:36:18
zephyr_这个菜鸡的脑子还是不干活/kk
by _5011_ @ 2020-07-05 22:37:23