HDU - 6968
共有n个科目,m套复习题。一套复习题对应一个科目,用时K天,可以获得J分。一个科目分数达不到60,即为挂科。问在X天,挂科数不超过Y科的情况下,最多能获得多少分?
01背包,求出在X天,每科可以获得最多分。
再求在挂科不超过Y,X天的情况下的最高分。
#include<bits/stdc++.h>
using namespace std;
struct node
{
int w[16000],v[16000];
int num;
} q[55];
int dp[55][550];
int g[55][505][4];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(dp,-0x3f,sizeof(dp));
memset(g,-0x3f,sizeof(g));
map<string,int> mp;
string s;
int n,i,j,l=1,a,b,m,k,t,f,P;
scanf("%d",&n);
for(i=0; i<n; i++)
{
cin>>s;
mp[s]=l;
q[i].num=0;
l++;
}
scanf("%d",&P);
while(P--)
{
cin>>s;
int k=mp[s];
int x=q[k].num;
scanf("%d %d",&a,&b);
q[k].w[x]=b;
q[k].v[x]=a;
q[k].num++;
}
scanf("%d %d",&m,&k);
for(i=1; i<l; i++)
{
dp[i][0]=0;
for(j=0; j<q[i].num; j++)
{
for(t=m; t>=q[i].w[j]; t--)
{
dp[i][t]=min(100,max(dp[i][t],dp[i][t-q[i].w[j]]+q[i].v[j]));
}
}
}
g[0][0][0]=0;
for(i=1; i<l; i++)
for(j=0; j<=m; j++)
for(int x=0; x<=k; x++)
for(f=0; f<=j; f++)
{
if(dp[i][f]>=60)
{
g[i][j][x]=max(g[i][j][x],g[i-1][j-f][x]+dp[i][f]);
}
else if(x)
{
g[i][j][x]=max(g[i][j][x],g[i-1][j-f][x-1]+dp[i][f]);
}
}
int ans=-1;
for(i=0; i<=k; i++)
ans=max(ans,g[n][m][i]);
printf("%d\n",ans);
}
}