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 啊?这样我也不知道错在哪里了啊