题解：#7534. 采购礼品

Teacher0329 qwq 2025-01-09 21:07:58 4

本题考点：并查集背包

查询 find函数

return x == f[x] ? x : f[x] = find(f[x]);

合并 merge函数

int fx = find(x);
int fy = find(y);
if (fx != fy)
    f[fx] = fy;

状态转移方程 dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

for (int j = maxn; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

1.输入和数组

2.每次输入、，合并

3.定义一个根，查找

if(f[i]!=i){
    root=find(i);
    w[root]+=w[i];
    v[root]+=v[i];
    w[i]=0;
    v[i]=0;
}

4.状态转移填数组

if(w[i]==0&&v[i]==0)continue;
for(int j=maxn;j>=w[i];j--)
    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

5.输出

题解：#7534. 采购礼品 审核通过