专栏文章

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

mmin_inf
P12444题解参与者 8已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@mipdq2hk
此快照首次捕获于
2025/12/03 10:19
3 个月前
此快照最后确认于
2025/12/03 10:19
3 个月前
查看原文
神奇 trick。
在 DFS 序上 DP，设 fi,jf_{i,j} 为 DFS 序在 [1,i)[1,i) 中的点代价为 jj 的答案。选 ii 这个点就转移到 i+1i+1，不选就转移到 endi+1end_i+1（即这个子树外）。
CPP
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]);
    }
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...