Proud Merchants HDU - 3466 | 有顺序的背包问题

好像是第一次接触有顺序的背包问题，之前做的背包都是乱序的，今天这两道题由于被其后效性左右，所以需要思考一下如何排序，这是关键。

题意：
每个物品有自己的价格Pi但是只有当手里的钱大于等于Qi时才可以购买，问最后在给定的钱的数目下能够买到的最大价值是多少。
分析：
对于相邻的两个物品，其购买顺序对于后面的物品没有影响，但是前一个物品可能会对后面的产生影响。
一个物品的价格差越大说明其对下一个越会产生影响（不知道这么理解对不对，dp的无后效性的证明对我而言一直都是个难题，不过从贪心的角度思考会更能说服我自己，不过贪心好像也很难证明。。。）

显然前者才是正确的
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(a) cout << "debug :" << a << endl
#define fi first
#define se second
const int maxn = 1e4;
const int inf = 0x3f3f3f3f;
struct node
{
    int p, q, v;
    bool operator< (const node& b)const
    {
        return q - p < b.q - b.p;
    }
}a[maxn];
int dp[maxn];
int n, m;

void init()
{
    mem(dp, 0);
}
int main()
{
    while(cin >> n >> m)
    {
        init();
        for(int i = 1; i <= n; i++)
            cin >> a[i].p >> a[i].q >> a[i].v;
        sort(a + 1, a + 1 + n);
        for(int i = 1; i <= n; i++)
            for(int j = m; j >= a[i].q; j--)
                dp[j] = max(dp[j], dp[j - a[i].p] + a[i].v);
        cout << dp[m] << endl;
        
    }
}