P6223 PODJELA

标签：P6223 int siz 数组 max PODJELA 节点 dp

2023.10.6 16:46 luogu solution

一道不错的树上背包题。

为了方便，我们先让拿到的钱减去给定值。那么此时因为要使所有农民的值 \(\ge 0\) 而每个节点只能通过它的祖先和其他的而非其子树节点沟通，所以我们先对于每个子树，让其所有非根值 \(\ge 0\) 求最小次数。这样参数还不够，那我们便在对应限制次数的基础上贪心地让根的值最大。设 \(dp_{i,u}\) 表示操作 \(i\) 次使得 \(u\) 的子树全达标，\(u\) 的最大值，那么对于此时我们加入的子节点 \(v\)，假设它的限制此数为 \(j\)，那么：
当 \(dp_{v,j}<0\) 时，我们一定要花一次使得其大于 \(0\)，那么有：

\[g_{i+j+1}=\max\{g_{i+j+1},dp_{v,j}+dp_{u,i}\} \]

（\(g[]\) 是临时数组）
否则，我们可以选择是否与 \(v\) 对应子树合并，有：

\[g_{i+j+1}=\max\{g_{i+j+1},dp_{v,j}+dp_{u,i}\}\\ g_{i+j}=\max\{g_{i+j},dp_{u,i}\} \]

然后注意一下代码细节即可。（用临时数组是因为我经常搞错转移顺序，而且有些背包题不能直接转移必须要临时数组，所以这里就直接用了）

\(Code\)

int n,f[N][N],siz[N],g[N];
vector<int>F[N];
void dfs(int x,int fa){
    for(int y:F[x])if(y^fa){
        dfs(y,x);
        for(int i=0;i<=siz[x]+siz[y];i++)g[i]=-1e9;//赋初值
        for(int i=0;i<siz[x];i++)
            for(int j=0;j<siz[y];j++){
                if(f[j][y]>=0)//可以不合并
                    g[i+j]=max(g[i+j],f[i][x]);
                g[i+j+1]=max(g[i+j+1],f[i][x]+f[j][y]);//合并
            }
        for(int i=(siz[x]+=siz[y]);~i;--i)//赋值回去
            f[i][x]=g[i];
    }
}
int main(){
    n=read();
    memset(f,-0x3f,sizeof(f));//赋初值
    for(int i=1,V=read();i<=n;i++)
        f[0][i]=V-read(),siz[i]=1;
    for(int i=1,u,v;i<n;i++)
        F[u=read()].push_back(v=read()),F[v].push_back(u);
    dfs(1,0);
    for(int i=0;i<=n;i++)
        if(f[i][1]>=0)
            return printf("%d",i),0;
}

end:17:01

标签：P6223,int,siz,数组,max,PODJELA,节点,dp
From： https://www.cnblogs.com/NBest/p/17744730.html