【HDU - 4341】Gold miner（分组背包）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 205
using namespace std;
struct node{
	int x,y,t,v;
}a[N];
int dp[40005],ans,g[N][N],cnt[N],p;
bool cmp(node a,node b){
	return a.x*b.y<a.y*b.x||a.x*b.y==a.y*b.x&&a.y<b.y;
}
int main() {
	int n,t,cas=0;
	while(~scanf("%d%d",&n,&t)){
		for(int i=1;i<=n;i++)
			scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].t,&a[i].v),
			cnt[i]=0;
		sort(a+1,a+1+n,cmp);
		memset(dp,0,sizeof dp);
		p=1;
		g[p][++cnt[p]]=1;
		for(int i=2;i<=n;i++)if(a[i].x*a[i-1].y==a[i].y*a[i-1].x){
			a[i].v+=a[i-1].v;
			a[i].t+=a[i-1].t;
			g[p][++cnt[p]]=i;
		}else{
			p++;
			g[p][++cnt[p]]=i;
		}
		for(int i=1;i<=p;i++)
			for(int j=t;j;j--)
				for(int k=1,v;k<=cnt[i];k++){
					v=g[i][k];
					if(j>=a[v].t)dp[j]=max(dp[j],dp[j-a[v].t]+a[v].v);
					else break;
				}
		printf("Case %d: %d\n",++cas,dp[t]);
	}
	return 0;
}