hdu 3535 AreYouBusy

// 混合背包
// xiaoA想尽量多花时间做ACM,但老板要求他在T时间内做完n堆工作,每个工作耗时ac[i][j],
// 幸福感ag[i][j],每堆工作有m[i]个工作,每堆工作都有一个性质,
// 0表示至少要做里面的1个工作,
// 1表示最多做里面的1个工作,
// 2表示随意,做或不做都行。最后问在符合老板要求的情况下的最大幸福感,怎么都不符合要求就输出-1. // 0 可以看 hdu 3033 I love sneakers!
// 1,2 情况就是普通背包了 #include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MOD 1000000007
#define maxn 110
int dp[maxn],dp_num[maxn],dpy[maxn];
int ac[maxn][maxn],ag[maxn][maxn];
int zero[maxn],one[maxn],two[maxn];
int main()
{
int n,T;
int m[maxn],s;
int num0,num1,num2;
int i,j,k;
while(scanf("%d %d",&n,&T)!=EOF){
num0=num1=num2=;
for(i=;i<=n;i++){
scanf("%d %d",&m[i],&s);
switch(s)
{
case :zero[num0++]=i;break;
case :one[num1++]=i;break;
case :two[num2++]=i;break;
}
for(j=;j<=m[i];j++)
scanf("%d %d",&ac[i][j],&ag[i][j]);
}
int num;
memset(dp,,sizeof(dp));
memset(dp_num,,sizeof(dp_num));
memset(dpy,,sizeof(dpy));
for(num=;num<num0;num++)
{
i=zero[num];
for(j=;j<=m[i];j++){
for(k=T;k>=ac[i][j];k--){
if(dpy[k]<dp[k-ac[i][j]]+ag[i][j]&&dp_num[k-ac[i][j]]>=num){
dpy[k]=dp[k-ac[i][j]]+ag[i][j];
dp_num[k]=num+;
} else if(dp_num[k]==num&&dp_num[k-ac[i][j]]==num){
dpy[k]=dp[k-ac[i][j]]+ag[i][j];
dp_num[k]=num+;
}
}
for(k=;k<=T;k++)
if(dpy[k]>dp[k])
dp[k]=dpy[k];
}
for(j=;j<=T;j++)
dp[j]=dpy[j];
}
num=;
for(j=;j<=T;j++)
if(dp_num[j]!=num0)
dpy[j]=dp[j]=-,num++;
// else
// printf("\n%d %d ]",j,dp[j]); if(num==T+){printf("-1\n");continue;}//
for(num=;num<num1;num++)
{
i=one[num];
for(j=;j<=m[i];j++)
for(k=T;k>=ac[i][j];k--)
if(dp[k-ac[i][j]]>-)
dpy[k]=max(dpy[k],dp[k-ac[i][j]]+ag[i][j]);
for(j=;j<=T;j++)
dp[j]=dpy[j];
}
// for(i=0;i<=T;i++) printf("\n %d %d ]",i,dpy[i]);
for(num=;num<num2;num++)
{
i=two[num];
for(j=;j<=m[i];j++)
for(k=T;k>=ac[i][j];k--)
if(dp[k-ac[i][j]]>-)
dp[k]=max(dp[k],dp[k-ac[i][j]]+ag[i][j]);
}
printf("%d\n",dp[T]);
} return ;
}
上一篇:整体二分QAQ


下一篇:css3新属性object-fit,对页面img处理