HDU 4341：Gold Miner（黃金礦工——分組 01 背包）

問題：原點 (0,0) 有 n 種金礦，座標 (x,y)、開採時間 t、價值 v。同一直線（斜率相同）的礦點必須按距離由近及遠順序開採。總時間限制 T，求最大價值。

分組背包建模

1. 按斜率 y/x 排序（避免除法用交叉乘積 y1*x2 < y2*x1），斜率相同按距離 x²+y² 升序。
2. 同斜率礦點歸為一組。組內物品：第 k 個礦點的「累積時間」= 前 k 個時間和，「累積價值」= 前 k 個價值和。每組最多選一個累積項（或不選）。
3. 標準分組 01 背包：dp[j] = max(dp[j], dp[j - t] + v)，外層遍歷組，中層容量逆序，內層遍歷組內選項。

代碼核心

sort(mines, mines+n, [](Mine a, Mine b){
    if (a.y*b.x == b.y*a.x) return a.x*a.x+a.y*a.y < b.x*b.x+b.y*b.y;
    return a.y*b.x < b.y*a.x;
});
// 分組
vector groups[210];
int cnt = 0;
groups[cnt].push_back(mines[0]);
for (i=1..n-1)
    if (same_slope(mines[i], mines[i-1])) groups[cnt].push_back(mines[i]);
    else groups[++cnt].push_back(mines[i]);
// 累積
for (g : groups)
    for (j=1; j=groups[i][0].t; j--)
        for (item : groups[i])
            if (j >= item.t) dp[j] = max(dp[j], dp[j-item.t]+item.v);

時間 O(nT)，空間 O(T)。經典分組背包變形題。