帮忙找找错吧

P1064 [NOIP2006 提高组] 金明的预算方案

白银新兵 @ 2016-09-18 23:28:42

/* 金明的预算方案:

第一次接触的“有依赖背包问题”

思想:

我们的目的便是把依赖背包换做我们原本学过的0/1背包

其中一种方法便是:

f[j]表示分配j元钱的包最多能获得的价格*期望值

让依赖条件成为一格背包中的一格分枝问题

这道题只有4种情况:

1)只买主件: f[j]=max(f[j],f[j-vi[i]]+ci[i])

2)买主件和它的一号附件:f[j]=max(f[j],f[ j- vi[i] - vi[next[i][1] ]+ci[i]+ci[next[i][1]]])

3) 买主件和它的二号附件:f[j]=max(f[j],f[ j- vi[i] - vi[next[i][2] ]+ci[i]+ci[next[i][2]]])

4) 买主件和所有附件:f[j]=max(f[j],f[ j - vi[i] - vi[next[j][1] - vi[next[i][2] ]+ci[i]+ci[next[i][1]]+ci[next[i][2]]]])

*/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int  n,m,q; 
bool ser[3205];    //判断    主件还是附件 1是主件,0是附件 
int f[33000];
int vi[3205];    //表示    价格 
int pi[3205];    //表示  期望值 
int ci[3205];   //表示  价格*期望值 
int next[1205][2];    //next[i][a]表示    主件i的a号附件 
int max(int a,int b){
    return a>b ? a : b;
}
void dp(){
    for(int i=1;i<=m;i++)    //枚举物品 
    for(int j=n;j>=vi[i];j--)    //枚举价格
    {
        if(ser[i]){    //是主件 
            f[j]=max(f[j],f[j-vi[i]]+ci[i]);
            if(j>=vi[i]+vi[next[i][1]])    f[j]=max(f[j],f[ j- vi[i] - vi[next[i][1] ]+ci[i]+ci[next[i][1]] ]);
            if(j>=vi[i]+vi[next[i][2]])    f[j]=max(f[j],f[ j- vi[i] - vi[next[i][2] ]+ci[i]+ci[next[i][2]] ]);
            if(j>=vi[i]+vi[next[i][1]]+vi[next[i][2]]) f[j]=max(f[j],f[ j - vi[i] - vi[next[i][1]] - vi[next[i][2] ]+ci[i]+ci[next[i][1]]+ci[next[i][2]] ]);
        }
    } 
}
int main(){
    cin>>n>>m;
    memset(next,0,sizeof(0));    //都没有附件 
    memset(ser,1,sizeof(1));
    memset(f,0,sizeof(0));    //初始化 
    for(int i=1;i<=m;i++){
        cin>>vi[i]>>pi[i]>>q;
        ci[i]=vi[i]*pi[i];
        if(q){    //是附件 
            ser[i]=0;
            if(!next[q][1]){    //目前该主件没有附件1 
                next[q][1]=i;
            }
            else next[q][2]=i;
        }     
        //主件不考虑 
    }
    dp();
    int ans=f[n];
    cout<<ans;
    return 0;
}

|