HDU 4341 Gold miner（分组背包）

题目链接 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;

}