90,有注释代码清楚,求大佬看看为什么wa2

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

Hopoyage @ 2024-09-29 17:40:37

int v[M];//体积
int w[M];//价值
int f[2][N][2];//进行了滚动数组优化
//f[i][j][k],前i个物品,体积为j,第i个物品选不选
vector<int>son[M];//记录各个主件的附件
bool flag[M];//标记主件

void solve(int times)
{
    int n,m;cin >> n >> m;
    int fa;
    for(int i = 1;i <= m;i++){
        cin >> v[i] >> w[i] >> fa;

        if(fa == 0){    
            flag[i] = 1;    //标记主件
        }else son[fa].push_back(i);

        w[i] = v[i]*w[i];
    }  

    for(int i = 1;i <= m;i++){  //枚举物品
        for(int j = 0;j <= n;j++){  //枚举体积
            if(!flag[i]){   //不是主件就只能不选当前物品
                f[i%2][j][0] = max(f[(i-1)%2][j][0],f[(i-1)%2][j][1]);
                continue;
            }

            //不选
            f[i%2][j][0] = max(f[(i-1)%2][j][0],f[(i-1)%2][j][1]);
            //只选主件不选附件
            if(j - v[i] >= 0)f[i%2][j][1] = max(f[(i-1)%2][j - v[i]][1],f[(i-1)%2][j - v[i]][0]) + w[i];
            //选一个附件
            if(son[i].size() == 1 && j - v[i] - v[son[i][0]] >= 0)f[i%2][j][1] = max(f[i%2][j][1],max(f[(i-1)%2][j - v[i] - v[son[i][0]]][1],f[(i-1)%2][j - v[i] - v[son[i][0]]][0]) + w[i] + w[son[i][0]]);
            if(son[i].size() == 2 && j - v[i] - v[son[i][1]] >= 0)f[i%2][j][1] = max(f[i%2][j][1],max(f[(i-1)%2][j - v[i] - v[son[i][1]]][1],f[(i-1)%2][j - v[i] - v[son[i][1]]][0]) + w[i] + w[son[i][1]]);
            //选两个附件
            if(son[i].size() == 2 && j - v[i] - v[son[i][1]] - v[son[i][0]] >= 0)f[i%2][j][1] = max(f[i%2][j][1],max(f[(i-1)%2][j - v[i] - v[son[i][0]] - v[son[i][1]]][1],f[(i-1)%2][j - v[i] - v[son[i][0]] - v[son[i][1]]][0]) + w[i] + w[son[i][0]] + w[son[i][1]]);
        }
    }

    cout << max(f[m%2][n][1],f[m%2][n][0]);
}

by jiqihang @ 2024-09-29 17:50:50

@Hopoyage 建议下载下来该数据,然后直接在代码前面对该数据的前几个数进行特判。就是直接输出。


by Hopoyage @ 2024-10-01 16:08:44

@jiqihang 啊?这样我也不知道错在哪里了啊


|