设为首页 加入收藏

TOP

HDU 3535 AreYouBusy
2015-11-21 01:00:06 来源: 作者: 【大 中 小】 浏览:1次
Tags：HDU 3535 AreYouBusy

分组背包

最多取一个的组，则对于该组来说，每一个状态只可能由前一组的状态过来，分不取和取两种

至少取一个，则没了不取的选择，即没有dp[i][j]=dp[i-1][j]的递推式

任意取，即01背包，取法包括由前一组不取或取一个，或由该组取一个

dp[i][j]表示前i组，消耗j时间所能取得的最大值

初值赋为-1，表示该状态不可达，对于dp[0]，初值赋为0，即什么都没有的时候最大的快乐值为0

还有一个要注意的点c[k]可能为0，会影响到递推式的顺序

?

发现做这种混合背包的题非常有助于弄清楚各种背包间的区别和联系

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               using namespace std; #define out(x) cout<<#x<<": "<
              
               >1; typedef long long ll; int c[maxn],g[maxn],dp[maxn][maxn]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif int n,t,m,s; while(scanf("%d%d",&n,&t)!=EOF){ memset(dp,-1,sizeof(dp)); memset(dp[0],0,sizeof(dp[0])); for(int i=1;i<=n;i++){ scanf("%d%d",&m,&s); for(int j=1;j<=m;j++) { scanf("%d%d",&c[j],&g[j]); } if(s==0){ for(int k=1;k<=m;k++){ for(int j=t;j>=c[k];j--){ if(dp[i][j-c[k]]!=-1) dp[i][j]=max(dp[i][j],dp[i][j-c[k]]+g[k]);//注意c[k]可能为0，所以这两句不能交换顺序，要不然dp[i][j-c[k]]的值就被改变了 if(dp[i-1][j-c[k]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-c[k]]+g[k]); } } } else if(s==1){ for(int j=0;j<=t;j++) dp[i][j]=dp[i-1][j]; for(int k=1;k<=m;k++){ for(int j=t;j>=c[k];j--){ if(dp[i-1][j-c[k]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-c[k]]+g[k]); } } } else { for(int j=0;j<=t;j++) dp[i][j]=dp[i-1][j]; for(int k=1;k<=m;k++){ for(int j=t;j>=c[k];j--){ if(dp[i][j-c[k]]!=-1) dp[i][j]=max(dp[i][j],dp[i][j-c[k]]+g[k]); } } } } int ans=-1; for(int i=0;i<=t;i++) ans=max(ans,dp[n][i]); printf("%d\n",ans); } return 0; }


?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：POJ1502 MPI Maelstrom Dijkstra 下一篇：sgu251：Polymania(构造)

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: