HDU 5410(2015多校10)-CRB and His Birthday(全然背包)-白红宇

HDU 5410(2015多校10)-CRB and His Birthday(全然背包)

阅读量：6120 次

发布时间：2019-06-21

本文共 1140 字，大约阅读时间需要 3 分钟。

题目地址：

题意：有M元钱，N种礼物，若第i种礼物买x件的话。会有Ai*x+Bi颗糖果，现给出每种礼物的单位价格、Ai值与Bi值。问最多能拿到多少颗糖果。

思路：全然背包问题。

dp[j][1]在当前物品时花钱为j的而且买过当前物品的最大值。

dp[j][0]不买当前这件物品此前花钱为j的的最大值。

每种物品的价值随Ai线性变化，可是不随B[i]线性变化。B[i]仅是在第一次挑选第i件物品是才算入，其它时候均不算入。

所以我们能够写出状态转移方程：

dp[j][0]=max(dp[j][1],dp[j][0]);

dp[j][1]=max(dp[j-q[i].w][0]+q[i].a+q[i].b,dp[j-q[i].w][1]+q[i].a);

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-7;const int Maxn=2010;struct node{ int a,b,w;}q[Maxn];int dp[Maxn][2];int main(){ int T,n,m,i,j; scanf("%d",&T); while(T--){ scanf("%d %d",&m,&n); for(i=1;i<=n;i++) scanf("%d %d %d",&q[i].w,&q[i].a,&q[i].b); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++){ for(j=0;j<=m;j++){ dp[j][0]=max(dp[j][1],dp[j][0]); if(j>=q[i].w) dp[j][1]=max(dp[j-q[i].w][0]+q[i].a+q[i].b,dp[j-q[i].w][1]+q[i].a); } } printf("%d\n",max(dp[m][0],dp[m][1])); } return 0;}

转载地址：http://hnmka.baihongyu.com/

你可能感兴趣的文章