题目链接 Gold miner
目标是要在规定时间内获得的价值总和要尽可能大。
我们先用并查集把斜率相同的物品分在同一个组。
这些组里的物品按照y坐标的大小升序排序。
如果组内的一个物品被选取了,那该组排在他前面的所有物品肯定被选取了。
那么我们对每个组的所有物品,对价值和代价分别求前缀和。
那么选了3号,就相当于选了1,2,3号。
这个时候问题就转化为分组背包了。
也就是说把物品转换后,这个组内我最多只能选1个物品。
然后就很简单了。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
typedef long long LL;
const int N = 205;
struct node{ int x, y, t, v; } a[N];
int father[N], used[N], c[N], f[N], g[N], dp[N * N];
int n, t, cnt, et, ca = 0;
vector <int> v[N];
int getfather(int x){ return father[x] ? father[x] = getfather(father[x]) : x; }
bool cmp(int p, int q){ return a[p].y < a[q].y;}
int main(){
while (~scanf("%d%d", &n, &t)){
rep(i, 1, n) scanf("%d%d%d%d", &a[i].x, &a[i].y, &a[i].t, &a[i].v);
memset(father, 0, sizeof father);
rep(i, 1, n - 1){
rep(j, i + 1, n){
if (a[i].x * a[j].y == a[i].y * a[j].x){
int fa = getfather(i), fb = getfather(j);
if (fa ^ fb){
father[fa] = fb;
}
}
}
}
rep(i, 1, n) c[i] = getfather(i);
rep(i, 0, n + 1) v[i].clear();
cnt = 0;
memset(used, 0, sizeof used);
rep(i, 1, n){
if (!used[c[i]]){
used[c[i]] = ++cnt;
v[cnt].push_back(i);
}
else{
v[used[c[i]]].push_back(i);
}
}
rep(i, 1, cnt) if ((int)v[i].size() > 1) sort(v[i].begin(), v[i].end(), cmp);
memset(dp, 0, sizeof dp);
rep(i, 1, cnt){
dec(j, t, 0){
int C = 0, V = 0;
for (auto u : v[i]){
C += a[u].t;
V += a[u].v;
if (j >= C) dp[j] = max(dp[j], dp[j - C] + V);
}
}
}
printf("Case %d: %d\n", ++ca, dp[t]);
}
return 0;
}