请选择 进入手机版 | 继续访问电脑版

树形DP刷题小记

[复制链接]
二次方先生 发表于 2021-1-3 12:14:15 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
树形DP刷题小记



最大子树和

链接:P1122 最大子树和
算法分析
典范的树形DP,要联合贪心的思想。f[x]存储以x为根可以得到的最大漂亮值,若子树的漂亮值小于零,即对效果有害,应减去。
状态转移方程:                                   f                         [                         x                         ]                         +                         =                         f                         [                         y                         ]                         >                         0                         ?                         f                         [                         y                         ]                         :                         0                              f[x]+=f[y]>0?f[y]:0                  f[x]+=f[y]>0?f[y]:0
Code:
[code]#includeusing namespace std;inline int Read(){        int dx=0,fh=1;        char c;        c=getchar();        while(c'9'){                if(c=='-')        fh=-1;                c=getchar();        }        while(c='0'){                dx=dx*10+c-'0';                c=getchar();        }        return dx*fh;}struct node{        int to,next;}edg[170000];int n,beauty[170000],h[170000],cnt,ans,f[170000];void add(int a,int b){        ++cnt;        edg[cnt].to=b;        edg[cnt].next=h[a];        h[a]=cnt;}void dfs(int u){        f=beauty;        for(int i=h;i;i=edg.next){                int v=edg.to;                dfs(v);                if(f[v]>0)        f+=f[v];        }        ans=max(ans,f);}int main(){        n=Read();        for(int i=1;i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )