偷天换日（树形DP）

Dear 丶 2021-11-09 08:04 328阅读 0赞

[洛谷][Link 1]

比较喜欢(≧∇≦)ﾉ这个建图  
对于叶子节点，直接处理出f\[i\]\[j\]当前i号节点分j个时间

#include<bits/stdc++.h>
    #define re return
    #define inc(i,l,r) for(int i=l;i<=r;++i)
    #define dec(i,l,r) for(int i=l;i>=r;--i)
    const int maxm=90005,maxn=1005;
    using namespace std;
    template<typename T>inline void rd(T&x)
    {
        char c;bool f=0;
        while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
        x=c^48;
        while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
        if(f)x=-x; 
    }
    
    
    int T,k,tot,cnt,hd[maxn],f[maxn][maxn];
    struct node{
        int to,nt,w;
    }e[maxn];
    inline void add(int x,int y,int z)
    {
     e[++k].to=y;e[k].nt=hd[x];hd[x]=k;e[k].w=z;
    } 
    inline void GET(int x)
    {
        int w,v;
        rd(w);w<<=1; 
        add(x,++cnt,w);
        w=cnt;
        rd(v);
        if(v){
            int vi,wi;
            inc(i,1,v)
            {
                rd(vi),rd(wi);
                dec(j,T-1,0)
                if(j<wi)break;
                else f[w][j]=max(f[w][j],f[w][j-wi]+vi);
            }
        }
        else
        {
            GET(w);
            GET(w);
        }
        
    }
    
    inline void DFS(int x)
    {
        for(int i=hd[x];i;i=e[i].nt)
        {
            int v=e[i].to;
            DFS(v);
            dec(j,T-1,0)
            inc(k,1,j-e[i].w)
            f[x][j]=max(f[x][j],f[x][j-k-e[i].w]+f[v][k]); 
        }
    }
    int main()
    {
        rd(T);
        GET(0);
        DFS(0);
        int ans=0;
        inc(i,0,T-1)
        ans=max(ans,f[0][i]);
        printf("%d",ans);
        re 0;
    }

转载于:https://www.cnblogs.com/lsyyy/p/11285584.html

[Link 1]: https://www.luogu.org/problem/P3360

发表评论取消回复

表情：

评论列表（有 0 条评论，328人围观）

还没有评论，来说两句吧...

相关阅读

相关树形DP：打家劫舍3

树形DP：打家劫舍3 问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0

系统管理员/ 2023年10月06日 13:58/ 0 赞/ 15 阅读

相关树形dp1

没有上司的舞会，树形dp include<bits/stdc++.h> define mms(a) memset(a,-1,sizeof(a)) u

超、凢脫俗/ 2023年08月17日 16:36/ 0 赞/ 136 阅读

相关树形DP例题

树形DP例题 DP感觉还是有点陌生，但是这个必须要强化，这类题型实在是太常见了 -------------------- 一、[题目链接：hdu 1520：Anni

忘是亡心i/ 2023年06月19日 06:47/ 0 赞/ 26 阅读

相关动态规划-树形DP

文章目录树形DP HDU-1520 HDU-2196 树形DP -------------------- 树形DP，顾名思义是在「树」这种数

淩亂°似流年/ 2023年03月04日 06:40/ 0 赞/ 214 阅读

相关 poj2342 树形dp入门

题意：公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系，求邀请哪些人来能使得晚会的总

心已赠人/ 2022年08月20日 16:06/ 0 赞/ 286 阅读

相关浅谈树形dp

总结：这一周重点训练了树形dp。对树形dp也有了一定的认识。先说一下总的观点吧。树形dp一般无非就是求出子节点的状态从而进一步去更新根节点的状态。一般的话，

系统管理员/ 2022年02月09日 10:53/ 0 赞/ 350 阅读

相关 uva10859 (树形dp)

题意：给你一个ｎ个点ｍ条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮。每盏灯将照亮以它为一个端点的所有边。在灯的总数最小的前提下，被两盏灯同时被照亮的边数应该尽量

青旅半醒/ 2021年12月14日 03:21/ 0 赞/ 358 阅读

相关 HDU - 2196（树形DP）

题目： A school bought the first computer some time ago(so this computer's id is 1). Durin

快来打我*/ 2021年11月26日 09:38/ 0 赞/ 318 阅读

相关 Computer HDU - 2196(树形dp)

题目要求:求树上每个点能到达的最远距离 dp\[u\]\[0\]：u的子树下u的最远距离是多少 dp\[u\]\[1\]：u的子树次远距离是多少 dp\[u\]\[

阳光穿透心脏的1/2处/ 2021年11月16日 11:14/ 0 赞/ 320 阅读

相关偷天换日（树形DP）

[洛谷][Link 1] 比较喜欢(≧∇≦)ﾉ这个建图对于叶子节点，直接处理出f\[i\]\[j\]当前i号节点分j个时间 include<bits/stdc

Dear 丶/ 2021年11月09日 08:04/ 0 赞/ 329 阅读