【题解】[TJOI2013] 黄金矿工 By 5ab as a juruo.

题目信息
分析
注意事项
Code

题目信息

题目来源：CCF 天津省选 2013；

在线评测地址：Luogu#3961；

运行限制：时间不超过 (1.00 extrm{s})，空间不超过 (128 extrm{MiB})。

题目描述

小 A 最近迷上了在上课时玩《黄金矿工》这款游戏。为了避免被老师发现，他必须小心翼翼，因此他总是输。

在输掉自己所有的金币后，他向你求助。每个黄金可以看做一个点（没有体积）。现在给出你 (N) 个黄金的坐标，挖到它们所需要的时间以及它们的价值。有些黄金在同一条直线上，这时候你必须按顺序挖。你可以瞬间把钩子转到任意角度。

请你帮助小 A 算出在时间 (T) 内他最多可以得到多少价值的金子。

输入格式

第一行两个整数 (N) 和 (T)，表示黄金的个数和总时间。

接下来 (N) 行，每行四个整数 (x)、(y)、(t)、(v)，分别表示黄金的坐标，挖到这个黄金的时间，以及这个黄金的价值。

输出格式

一个整数,表示你可以在 (T) 时间内得到的最大价值。

数据规模与约定

对于 (30\%) 的数据，(0<Tle 4 imes 10^3)；
对于 (100\%) 的数据，(1le Nle 200)，(0<Tle 4 imes 10^4)。

保证 (0le|x|le 200)，(0<y≤200)，(0<tle 200)，(0le vle 200)。

分析

一道不错的约束背包入门题。我们直接分析正解。~~我实在不知道 30% 那档部分分有什么意义~~

首先，如果没有一条直线上的约束条件，这道题就是一道不折不扣的简单背包题。然而这道题有这个鬼畜的约束条件，那么怎么做呢？

注意到这个约束条件是要先选了什么，然后才能选什么的结构，所以我们可以将这些东西打包，要选就一起选。

然而，如果这样做 0/1 背包的话就可能得到 (0) 分的好成绩，因为在这种情况下，小包和大包一起选是合法的，但是这么做不符合题意。那么怎么办呢？

我们考虑对 0/1 背包做一点小小的改动。显然，在一般的 0/1 背包模板中，这两个情况不是同时转移的，这就导致这两种情况可能同时选上。那么，我们能否将这两个转移放在一起呢？

考虑滚动数组，我们在做背包的时候，如果目前的在同一条链上，那么就先不滚动，当这条链上的所有情况都转移完毕以后再滚动。这样就可以避免一条链上选多组。由于每一个点只会访问一次，所以复杂度是那个经典的 (mathcal{O}(NT))。

注意事项

打包前不要忘了给数组排序；
DP 背包数组要比最大消费多开 (1) 个；
滚动数组之前要先拷贝一份。

Code

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int max_n = 200, max_w = 40000;

struct srt
{
	int val, id;

	srt(int _v = 0, int _i = 0) : val(_v), id(_i) { }

	operator int() const
	{
		return id;
	}

	bool operator<(const srt& s) const
	{
		return val < s.val;
	}
};

vector<srt> g[max_n];
int w[max_n], v[max_n], ax[max_n], ay[max_n], bel[max_n], dp[2][max_w+1] = {}, ind = 0;

inline int my_abs(int x) { return (x < 0)? -x:x; }

int main()
{
	memset(bel, -1, sizeof(bel));

	int n, mxw, tw, tv, *res = dp[1], *prv = dp[0];
	bool flag = false;

	scanf("%d%d", &n, &mxw);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d%d%d", ax + i, ay + i, w + i, v + i);
		flag = false;

		for (int j = 0; j < i; j++) // 这里写成 ind 更好
			if (ax[j] * ay[i] == ax[i] * ay[j]) // 在一条直线上
			{
				g[bel[j]].push_back(srt(my_abs(ax[i]), i)); // 推进去
				flag = true, bel[i] = bel[j];

				break;
			}
		
		if (!flag) // 不与任何一个在一条直线上
		{
			g[ind].push_back(srt(my_abs(ax[i]), i)); // 自己创建一个
			bel[i] = ind++;
		}
	}

	for (int i = 0; i < ind; i++) // 遍历每一条直线
	{
		sort(g[i].begin(), g[i].end()); // 排序
		tw = 0, tv = 0;

		for (int p = 0; p < g[i].size(); p++) // 遍历每一组
		{
			tw += w[g[i][p]], tv += v[g[i][p]]; // 计算总时间和收益
			
			for (int j = tw; j <= mxw; j++)
				res[j] = max(prv[j], prv[j-tw]+tv); // 背包转移
		}
		
		swap(prv, res); // 滚动数组
		memcpy(res, prv, sizeof(dp[0]));
	}

	printf("%d
", prv[mxw]); // 输出

	return 0; // 然后就 AC 了、
}