BUPT2017 wintertraining(15) #8B

题意

给出每个黄金的坐标、价值及耗时，同一方向的黄金只能依次取，求T时间内收获的最大值。

题解

同一方向，物品前缀和构成的组合，相当于是一个分组的物品。

然后分组背包：

for i:1~p个分组

for j:T~1的时间（背包容量）

for k:1~当前分组物品数

if(j>=t[k])dp[j]=max(dp[j], dp[j-t[k]]+v[k])

因为我们的t[k+1]一定大于t[k]，所以else的时候可以直接break。

#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;

}