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

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