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。
代码语言：javascript复制#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: %dn", cas,dp[t]);
}
return 0;
}
