首页 > 其他 > 详细

Comet OJ - Contest #11 B 背包dp

时间:2019-09-23 18:45:08      阅读:129      评论:0      收藏:0      [点我收藏+]

Code: 

#include <bits/stdc++.h> 
#define N 1005   
#define M 2000
#define setIO(s) freopen(s".in","r",stdin)   
using namespace std;     
int A[N],B[N],w[M+3],f[M+3];        
int main() 
{ 
    // setIO("input");   
    int n,m,k,i,j,ans=0;    
    scanf("%d%d%d",&n,&m,&k);     
    for(i=0;i<=k;++i) scanf("%d",&w[i]);       
    for(i=1;i<=m;++i) scanf("%d%d",&A[i],&B[i]);      
    memset(f,-1,sizeof(f));          
    f[0]=0;      
    for(i=1;i<=n;++i) 
    {
        for(j=M;j>=0;--j) 
        {   
            if(f[j]==-1) continue;     
            for(int tmp=1;tmp<=m;++tmp) 
            {
                if(j>=A[tmp])             
                    f[j-A[tmp]]=max(f[j-A[tmp]], f[j]+B[tmp]);     
            }
        }  
        if(i!=n) 
        { 
            for(j=M;j>=0;--j) 
            { 
                if(f[j]==-1) continue;      
                f[j+w[j]]=max(f[j+w[j]], f[j]);   
            }  
        } 
    }
    for(j=0;j<=M;++j) 
    { 
        if(f[j]==-1) continue;        
        ans=max(ans, f[j]+w[j]+j);    
    }
    printf("%d\n",ans); 
    return 0; 
}

  

Comet OJ - Contest #11 B 背包dp

原文:https://www.cnblogs.com/guangheli/p/11573868.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!