hdu4341(分組背包)

Gold miner

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1444    Accepted Submission(s): 575

Problem Description Homelesser likes playing Gold miners in class. He has to pay much attention to the teacher to avoid being noticed. So he always lose the game. After losing many times, he wants your help.

To make it easy, the gold becomes a point (with the area of 0). You are given each gold's position, the time spent to get this gold, and the value of this gold. Maybe some pieces of gold are co-line, you can only get these pieces in order. You can assume it can turn to any direction immediately.

Please help Homelesser get the maximum value.  

Input There are multiple cases.

In each case, the first line contains two integers N (the number of pieces of gold), T (the total time). (0＜N≤200, 0≤T≤40000)

In each of the next N lines, there four integers x, y (the position of the gold), t (the time to get this gold), v (the value of this gold). (0≤|x|≤200, 0＜y≤200,0＜t≤200, 0≤v≤200)  

Output Print the case number and the maximum value for each test case.  

Sample Input

3 10
1 1 1 1
2 2 2 2
1 3 15 9
3 10
1 1 13 1
2 2 2 2
1 3 4 7
        

Sample Output

Case 1: 3
Case 2: 7
        

Author HIT  

Source 2012 Multi-University Training Contest 5   本題要求在給定時間下盡可能多的找到金子， 同一方向是有先後順序的，不同方向可以任意轉換。 同一方向是有先後順序的，不同方向可以任意轉換，我們的在這句話上挖掘有用資訊，及同一方向不能跳躍。若我們把同一方向的時間、價值累加，就形成了等價且數目相同的互斥事件，即在同一方向上隻能取一個。統計出不同方向數、每個方向事件數結合規定時間T，就可以找到對應的模型-分組背包。即把物品分組，每組内隻能取一個（不能同時取多個），狀态轉移方程為：               dp[k][j]=max(dp[k-1][j],dp[k-1][j-t[i]]+v[i]),i屬于小組k

for 所有的組k      

    for v=V..0      

        for 所有的i屬于組k      

            f[v]=max{f[v],f[v-c[i]]+w[i]}      

對于本題，怎麼分組呢？由于是從原點出發，是以很快就能想到應按斜率分組（大小順序任選），在斜率相同即屬于同一組時按據原點距離從小到大排序（這點很重要-因為我們要累加同一方向時間、價值的）。      

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

struct node
{
	int x,y,t,val;
}Point[200+20];
int num,tim;
int group[200*2+20][200+10];
int dp[40000+100];
int cnt;

bool cmp(node a,node b)//在題目明确給出的條件下此函數即可保證先按斜率從小到大，再按距離遠點距離從小到大排序
{
	if(a.x*b.y!=a.y*b.x)
		return a.y*b.x<a.x*b.y;
	return a.y<b.y;
}

int Max(int a,int b)
{
	return a<b?b:a;
}

void GroupPack()
{
	int i,j,k;
	memset(dp,0,sizeof(dp));
	for(i=0;i<cnt;i++)
	{
		//printf("********%d\n",group[i][0]);
		for(j=tim;j>=0;j--)
		{
			for(k=1;k<=group[i][0];k++)
			{
				if(j>=Point[group[i][k]].t)
					dp[j]=Max(dp[j],dp[j-Point[group[i][k]].t]+Point[group[i][k]].val);
			}
		}
	}
}

int main()
{
	int i,tag=1;
	while(~scanf("%d%d",&num,&tim))
	{
		for(i=0;i<num;i++)
			scanf("%d%d%d%d",&Point[i].x,&Point[i].y,&Point[i].t,&Point[i].val);
		sort(Point,Point+num,cmp);

		cnt=0;
		for(i=0;i<num;i++)
		{
			group[cnt][0]=0;
			group[cnt][++group[cnt][0]]=i;
			for(i++;i<num;i++)
			{
				if(Point[i].x*Point[i-1].y==Point[i-1].x*Point[i].y)
				{
					Point[i].val+=Point[i-1].val;
					Point[i].t+=Point[i-1].t;
					group[cnt][++group[cnt][0]]=i;
				}
				else 
				{
					i--;
					break;
				}
			}
			cnt++;
		}

		GroupPack();
		printf("Case %d: %d\n",tag++,dp[tim]);
	}
	return 0;
}