题解：P12444 [COTS 2025] 发好奖 / Hijerarhija

min_inf · 2025-05-08 12:46:26 · 题解

神奇 trick。

在 DFS 序上 DP，设 f_{i,j} 为 DFS 序在 [1,i) 中的点代价为 j 的答案。选 i 这个点就转移到 i+1，不选就转移到 end_i+1（即这个子树外）。

rep(i,1,n){
    int u=rdfn[i];
    rep(j,0,m){
        chkmax(dp[ed[u]+1][j],dp[i][j]);
        if(j<m)chkmax(dp[i+1][j+1],dp[i][j]);
        if(j+c[u]<=m)chkmax(dp[i+1][j+c[u]],dp[i][j]+p[u]);
    }
}