题目链接：

[TJOI2013]黄金矿工 - 洛谷https://www.luogu.com.cn/problem/P3961

思路：

是一个经过变形的01背包题，被挡住的金子不能立刻拿到，（用斜率判断是否在同一直线上，即可知道有没有被挡住），要把其前面的金子拿了才能拿。所以把他们放在一组处理（在代码实现上，需要用二维数组来装物品，一组的放一起）。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef  long long int ll;
const double eps = 1e-6; //斜率判断误差值
const int maxn = 1e5+5;
int n,m; //黄金个数，时间
vector<int> val[maxn]; //价值（分组后）
vector<int> cost[maxn]; //耗时（分组后）
int dp[maxn]; // dp[j]表示背包容量为j的时候能得到的最大val值
struct node{
    int x, y, t, v; //坐标，时间，价值
    double k; //斜率
} gold[maxn];

bool cmp(node a, node b){
    //斜率小的在前面，坐标小的在前面
    //斜率第一顺序，坐标第二顺序（这主要是为了让斜率相同的点排在一起，并且先拿到的放前面，方便后续处理）
    if(abs(a.k-b.k) < eps){ //斜率相等
        return a.x < b.x;
    }
    else return a.k < b.k;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> gold[i].x >> gold[i].y >> gold[i].t >> gold[i].v;
        gold[i].k = (double)gold[i].y / gold[i].x; //计算斜率
    }
    sort(gold+1, gold+n+1, cmp); //排序


    // 进行背包分组
    int idx = 1; //当前分组物品位置
    val[1].push_back(gold[1].v);
    cost[1].push_back(gold[1].t);
    double curK = gold[1].k;
    for(int i=2; i<=n; i++){
        if(abs(gold[i].k - curK) < eps){
            val[idx].push_back(gold[i].v);
            cost[idx].push_back(gold[i].t);
        }else{
            idx++;
            val[idx].push_back(gold[i].v);
            cost[idx].push_back(gold[i].t);
        }
    }

    //开始分组背包dp
    for(int i=1; i<=idx; i++){ //遍历物品（分组之后的）
        for(int j=m; j>=cost[i][0]; j--){ //遍历背包空间，能装下当前第一个物品才进入循环（是为了剪枝）
            int have = j; //目前剩余的空间
            int value = 0; //目前在这组物品里拿到的价值
            for(int k=0; k<cost[i].size(); k++){ //遍历这一组的所有物品
                if(have >= cost[i][k]){
                    have -= cost[i][k];
                    value += val[i][k];
                    dp[j] = max(dp[j], dp[have] + value);
                }
                else break; //当前物品拿不到，后面的也不能拿了
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}

看了别的大佬的代码，发现还有另一种处理方式，在分组的时候直接存储前缀和，代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef  long long int ll;
const double eps = 1e-6;
const int maxn = 1e5+5;
int n,m; //黄金个数，时间
vector<int> val[maxn]; //价值（分组后）
vector<int> cost[maxn]; //耗时（分组后）
int dp[maxn]; // dp[j]表示背包容量为j的时候能得到的最大val值
struct node{
    int x, y, t, v; //坐标，时间，价值
    double k; //斜率
} gold[maxn];

bool cmp(node a, node b){
    //斜率小的在前面，坐标小的在前面
    //斜率第一顺序，坐标第二顺序
    if(abs(a.k-b.k) < eps){ //斜率相等
        return a.x < b.x;
    }
    else return a.k < b.k;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> gold[i].x >> gold[i].y >> gold[i].t >> gold[i].v;
        gold[i].k = (double)gold[i].y / gold[i].x; //计算斜率
    }
    sort(gold+1, gold+n+1, cmp); //排序


    // 进行背包分组
    int idx = 1; //当前分组物品位置
    val[1].push_back(gold[1].v);
    cost[1].push_back(gold[1].t);
    double curK = gold[1].k;
    for(int i=2; i<=n; i++){
        if(abs(gold[i].k - curK) < eps){
            val[idx].push_back(gold[i].v);
            cost[idx].push_back(gold[i].t);
            //下面是前缀和处理
            int size = val[idx].size();
            if(size > 1){
                val[idx][size-1] += val[idx][size-2];
                cost[idx][size-1] += cost[idx][size-2];
            }
        }else{
            idx++;
            val[idx].push_back(gold[i].v);
            cost[idx].push_back(gold[i].t);
        }
    }

    //开始分组背包dp
    for(int i=1; i<=idx; i++){ //遍历物品
        for(int j=m; j>=cost[i][0]; j--){ //遍历背包空间，能装下当前第一个物品才进入循环
            for(int k=0; k<cost[i].size(); k++){
                if(j>=cost[i][k]) dp[j] = max(dp[j], dp[j-cost[i][k]] + val[i][k]);
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}