hdu 4341 Gold miner(分組01背包)

http://acm.hdu.edu.cn/showproblem.php?pid=4341

看到這個圖好親切，黃金礦工，很好玩的游戲。。。

題意：礦工起初在(0,0)位置，有n種金礦，給出每種金礦的坐標，花費時間和價值。在同一條線上的金礦必須先抓近的再抓遠的，若近的不抓沒辦法抓遠的。要求在T時間內獲得的最大價值。

思路：01背包問題，但需要變形。 變形之處就是解決在同一條線上的金礦。 分組背包，把在同一條線上的金礦分為同一組。先按斜率排序，斜率相等按距離排序。例如1,2,3,4,5，五種金礦，根據斜率計算出1和2；3和4斜率分別相等，那麼可分為（1,2）（3,4）（5）三組。在這裡由於先抓近的再抓遠的，對於（3,4）一組，把3物品的時間和價值加到4物品上作為4物品的時間和價值。這樣就對應了分組背包每組最多取一件。 形成分組背包模型後直接套模板。

#include 
#include 
#include 
#include 
using namespace std;

int n,T;
struct node
{
	int x,y;
	int t,v;
	bool operator < (const struct node &tmp)const
	{

		if(y*tmp.x == x*tmp.y)//斜率相等，按距離從小到大排序，不能按y/x排，因為x可能為0.
			return y < tmp.y;
		return y*tmp.x < x*tmp.y;
	}
}point[210];

vector  edge[210];//保存分組後的狀態
int cnt;
int dp[40010];

int solve()
{
	memset(dp,0,sizeof(dp));
	for(int i = 0; i <= cnt; i++)
	{
		for(int j = T; j >= edge[i][0].t; j--)
		{
			for(int k = 0; k < (int)edge[i].size(); k++)
				dp[j] = max(dp[j], dp[j-edge[i][k].t]+edge[i][k].v);
		}
	}
	return dp[T];
}

int main()
{
	int item = 1;
	while(~scanf("%d %d",&n,&T))
	{
		for(int i = 0; i < n; i++)
			scanf("%d %d %d %d",&point[i].x,&point[i].y,&point[i].t,&point[i].v);


		sort(point,point+n);

		for(int i = 0; i < n; i++)
			edge[i].clear();

		cnt = 0;
		edge[cnt].push_back(point[0]);

		for(int i = 1; i < n; i++)	//n件物品分組
		{
			if(point[i].x*point[i-1].y == point[i].y*point[i-1].x)
				edge[cnt].push_back(point[i]);
			else edge[++cnt].push_back(point[i]);
		}

		for(int i = 0; i <= cnt; i++)
		{
			//修改同一條線上的金礦的時間和價值
			for(int j = 1; j < (int)edge[i].size(); j++)
			{
				edge[i][j].t += edge[i][j-1].t;
				edge[i][j].v += edge[i][j-1].v;
			}
		}
		printf("Case %d: %d\n",item++,solve());
	}
	return 0;
}