求大佬看看哪里有问题

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

Alien_worm @ 2018-05-05 23:38:24

#include <iostream>
#include <algorithm>

using namespace std;

struct node{
    int v[3], p[3]; // v[0],p[0]主件,v[1],v[2],p[1],p[2]附件 
    int fj; // 附件个数 
}x[65]; 
int dp[32222];

int main(){
    int n, m, re, cnt = 0, f = 1;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int v, p, q;
        cin >> v >> p >> q;
        if(q == 0){
            x[cnt].v[0] = v;
            x[cnt].p[0] = v * p;    
            re = cnt;
            f = 1; 
            cnt++;
        }
        else{
            x[re].v[f] = v;
            x[re].p[f] = v * p;             
            x[re].fj++;
            f++;
        }
    }
    for(int i = 0; i < cnt; i++){
        for(int j = n; j >= x[i].v[0]; j--){
            if(x[i].fj == 0){ // 只有主件 
                dp[j] = max(dp[j], dp[j-x[i].v[0]] + x[i].p[0]);    
            }   
            else if(x[i].fj == 1){ // 有一个附件 
                dp[j] = max(dp[j], dp[j-x[i].v[0]] + x[i].p[0]);
                if(j-x[i].v[0]-x[i].v[1] >= 0)
                    dp[j] = max(dp[j], dp[j-x[i].v[0]-x[i].v[1]] + x[i].p[0] + x[i].p[1]);
            }
            else if(x[i].fj == 2){ // 有两个附件 
                dp[j] = max(dp[j], dp[j-x[i].v[0]] + x[i].p[0]);
                if(j-x[i].v[0]-x[i].v[1] >= 0) // 选主件和附件一 
                    dp[j] = max(dp[j], dp[j-x[i].v[0]-x[i].v[1]] + x[i].p[0] + x[i].p[1]);
                if(j-x[i].v[0]-x[i].v[2] >= 0) // 选主件和附件二 
                    dp[j] = max(dp[j], dp[j-x[i].v[0]-x[i].v[2]] + x[i].p[0] + x[i].p[2]);
                if(j-x[i].v[0]-x[i].v[1]-x[i].v[2] >= 0) // 选主件和附件一附件二 
                    dp[j] = max(dp[j], dp[j-x[i].v[0]-x[i].v[1]-x[i].v[2]] + x[i].p[0] + x[i].p[1] + x[i].p[2]);
            }
        }
    }
    cout << dp[n] << endl;
} 

by WorldBest丶牛顿 @ 2018-05-06 06:43:30

感觉是不是前面f有问题,如果两个主件相同的附件不相邻的话就会出错

不如直接用fj代替f存数组


|