`
yzmduncan
  • 浏览: 330292 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论
阅读更多

    树形DP,即是在一颗树上进行DP,一般是有叶子节点状态推出根节点状态。结合几个简单例子分析。

例1. POJ2342/POJ3342

【题意】

公司有n个人,每个人有价值vi,有一天举办年会,每个人都可以参加,但有严格的等级制度,参加活动时,不能同时出现a和a的上司,问如何才能使总和最大。

【分析】

每个人只有去和不去两种状态,设DP[i][0]和DP[i][1]分别表示第i个人不参加和参加年会,获得的总的最大价值。

则状态转移方程为:

DP[i][1] += DP[j][0],

DP[i][0] += max{DP[j][0],DP[j][1]};其中j为i的孩子节点。

这样,从根节点r进行dfs,最后结果为max{DP[r][0],DP[r][1]}。

POJ3342与上面类似,多了一个问题问最后最大的结果是不是唯一的,判断唯一性:当某个节点i取不取一样,并且它的某个孩子节点取不取一样,那么结果才不唯一。


例2. HDU2196

【题意】

一棵树,询问一颗树上每个点离它最远的点是哪个?

【分析】

一棵树上离它最远的点必定在树的直径上(否则可以找到离它更远的点),到底是两端点的哪个点呢?

求树的直径:从任意一点BFS,得到最远点k,则k点必定是树的直径其中一端点,再从k点BFS,得到另一端点j,在求解过程中用两个数组记录其它点到这两点的距离,最后比较较大者为答案。


例3. POJ1463

【题意】


一颗树,n个节点,现在要在节点处设置尽量少的哨兵,使得每条边都被观察到。

【分析】

一个节点要么设立哨兵,要么不设立,若节点i不设立哨兵,则节点i的所有的孩子节点必须设立哨兵;否则,看若节点i的孩子设立哨兵的值是否

小于不设哨兵的值,取二者中的较小者。

DP[i][0] = sum{DP[j][1]},

DP[i][1] = sum{min(DP[j][1],DP[j][0])} + 1, j是i的孩子节点。



例4. POJ4045

【题意】

n个城市节点构成的一棵树,节点i和节点j的电量损耗为I*I*R*i到j的路径所含边数,现在要修建一个供电站,使得总的损耗量最小。求最小

损耗和可以修建供电站的节点。

【分析】

一种简单的想法就是枚举所有节点,然后bfs求和,复杂度为O(n^2)。

首先,选定任意一点作为根节点dfs,设两个数组num[i]和dp[i],分别表示以节点i为根的子树的节点个数 和 根到其子节点的距离(边数)之和。

num[i] = sum{num[j]}+1,dp[i] = sum{num[j]+dp[j]}.

从root开始第二次dfs,依次考虑每个点作为根节点,考虑将x(当前根节点)的孩子y作为根节点:

dp[y] = dp[y] + (dp[x]-dp[y]-num[y])+(num[x]-num[y]) = dp[x]-2*num[y] + num[x],记录最小值即可。

附POJ2342和POJ4045代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int Max = 6005;

struct Node
{
    int fa;
    int value;
    vector<int> child;
}node[Max];
int dp[Max][2];
bool vis[Max];

int max(int a, int b)
{
    return a>b?a:b;
}

void dfs(int now)
{
    vis[now] = true;
    int s = node[now].child.size();
    for(int i = 0; i < s; i++)
    {
        int child = node[now].child[i];
        if(!vis[child])
        {
            dfs(child);
            dp[now][1] += dp[child][0];
            dp[now][0] += max(dp[child][0],dp[child][1]);
        }
    }
}

int main()
{
    int i;
    int a,b;
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(node,0,sizeof(Node));
        memset(vis,0,sizeof(vis));
        for(i = 1; i <= n; i++)
        {
            scanf("%d",&dp[i][1]);
            dp[i][0] = 0;
        }
        while(scanf("%d %d",&a,&b)!=EOF)
        {
            if(a==0&&b==0)
                break;
            node[a].fa = b;
            node[b].child.push_back(a);
        }
        int root = 1;
        for(i = 1; i <= n; i++)
        {
            if(!node[i].fa)
            {
                root = i;
                break;
            }
        }
        dfs(root);
        printf("%d\n",max(dp[root][0],dp[root][1]));
    }
    return 0;
}
 #include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int Max = 51000;
typedef __int64 int64;
int n;
int I,R;

struct Edge
{
    int to;
    int next;
}e[Max*2];
int head[Max],numm;
bool vis[Max];
int64 dp[Max],num[Max];

void addEdge(int from, int to)
{
    e[numm].to = to;
    e[numm].next = head[from];
    head[from] = numm++;
}

void dfs1(int now)
{
    dp[now] = 0;
    num[now] = 1;
    vis[now] = true;
    for(int i = head[now]; i != -1; i = e[i].next)
    {
        int next = e[i].to;
        if(!vis[next])
        {
            dfs1(next);
            num[now] += num[next];
            dp[now] += dp[next]+num[next];
        }
    }
}

void dfs2(int now)
{
    vis[now] = true;
    for(int i = head[now]; i != -1; i = e[i].next)
    {
        int next = e[i].to;
        if(!vis[next])
        {
            dp[next] = dp[now] - 2*num[next] + n;
            dfs2(next);
        }
    }
}

int main()
{
    int i,j;
    int t;
    int x,y;
    scanf("%d",&t);
    while(t--)
    {
        numm = 0;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        scanf("%d %d %d",&n,&I,&R);
        for(i = 1; i < n; i++)
        {
            scanf("%d %d",&x,&y);
            addEdge(x,y);
            addEdge(y,x);
        }
        dfs1(1);
        memset(vis,0,sizeof(vis));
        dfs2(1);
        int64 result = ((int64)1)<<61;
        vector<int> ans;
        ans.clear();
        for(i = 1; i <= n; i++)
        {
            if(dp[i]<result)
            {
                ans.clear();
                ans.push_back(i);
                result = dp[i];
            }
            else if(dp[i]==result)
                ans.push_back(i);
        }
        printf("%I64d\n",result*I*I*R);
        int r = ans.size();
        for(i = 0; i < r; i++)
        {
            printf("%d",ans[i]);
            printf("%c",i==r-1?'\n':' ');
        }
        printf("\n");
    }
    return 0;
}
 
分享到:
评论

相关推荐

    树形 DP 算法 文档

    ### 树形DP算法在立体对应中的应用 #### 概述 本文档主要介绍了一种改进的立体对应算法——基于树形动态规划(Tree-shaped Dynamic Programming, TDP)的方法。传统立体对应方法通常沿扫描线应用动态规划技术,这种...

    ThinkMap-实现Android端的简易思维导图。可以保存数据。编辑树形图。.zip

    核心实现分布如下:2017-07-01TreeModel:树形结构的存储,树形结构的遍历,添加、删除节点;NoteModel:节点关联的指向,和Parent的指向;TreeView :绘制树形结构,对树形结构位置的纠正,实现View层的添加,删除,...

    各种动态规划问题(DP)的整理和归纳,超详细的!千万不要只看一眼哦

    1. 树形DP:这种类型的动态规划常用于处理树结构的问题,如树的直径、最近公共祖先(LCA)等问题。我们通常将问题分解为节点间的子问题,并沿着树的边进行转移。 2. 状态压缩DP:状态压缩是为了节省空间,通常用于...

    动态规划的一些简单问题课件

    线性DP通常处理与数组或序列相关的问题,区间DP处理涉及区间操作的问题,而树形DP则应用于树结构的数据,如最小生成树、树上最短路径等。 总结来说,动态规划是一种强大的算法工具,能够有效地解决各种优化问题,...

    北大acm试题分类~~~

    - **问题1112**:中等难度,涉及树形DP,推荐参考《算法艺术与信息学竞赛》中的相关章节。 - **问题1848**:同样为树形DP,适合深入理解树状模型的应用。 - **问题1234, 1947, 1946, 1737**:这些题目均来自《算法...

    DP.rar_againstriy

    3. 树形动态规划:如树的直径问题,问题涉及树结构的最优属性。 4. 图形动态规划:如最短路径问题,问题涉及图的最优路径。 五、动态规划与分治法、贪心法的区别 1. 分治法:将大问题拆分为小问题,独立解决后再...

    《算法艺术与信息学竞赛》在pku等网站上的题目

    树形DP是动态规划的一种重要变体,常应用于树结构或图结构问题中。 - **减少冗余计算**:题目[1821](http://acm.pku.edu.cn/JudgeOnline/problem?id=1821)需要通过优化状态转移方程来减少不必要的计算量。这类题目...

    牛客 – 王国(虚树+树的直径)

    题目分析:真的很巧,上周刚学的虚树,读完这个题的第一反应就是可以用虚树简化题目,其实完全可以用树形dp跑一遍dfs出来,可奈何我dp不好,就只能用虚树来做了 题目中有两个点可以单独考虑,首先是权值相同的点,这...

    动态规划30道经典问题图解解析(bigsai本人原创)

    动态规划是一种解决问题的有效方法,尤其在算法领域,它在处理具有重叠子问题和最优子结构的复杂问题时显得尤为强大。...对于更高级的动态规划问题,如树形dp、状态压缩等,需要更深入的学习和实践。

    算法基础课程:算法备赛学程

    算法基础课程 算法准备赛学程序目标:1.基础算法分级二分高精度垂直和与差分双指针算法位置运算离散化区间合并 ...背包问题线性DP区间DP计数类DP数位统计DP状态压缩DP树形DP记忆化搜索 6.贪心 7.时空复杂度分析

    15届蓝桥杯知识点大纲

    13. DP:包括背包DP、树形DP、状压DP、数位DP等高级动态规划算法。 14. 字符串:包括哈希、KMP、Manacher等字符串处理算法。 15. 图论:包括欧拉回路、最小生成树、单源最短路及差分约束系统、拓扑序列、二分图匹配...

    leetcode中国-leetcode_algo:leetcode相关算法和模板使用python

    树形DP 记忆化搜索 贪心 时空复杂度分析 提高知识点 动态规划——从集合角度考虑DP问题 1.1 数字三角形模型 1.2 最长上升子序列模型 1.3 背包模型 1.4 状态机模型 1.5 状态压缩DP 1.6 区间DP 1.

    基础算法 第9章 第1节 动态规划基础(C++版)-2021.02.10.pdf

    树形动规适用于树形结构或者需要递归分解的问题,例如贪吃的九头龙、数字三角形等;背包问题是一类特殊的优化问题,涉及的是物品选择与价值最大化,包括01背包问题、完全背包问题等多种变体。 在动态规划算法中,...

    2020_CSP-J、CSP-S注意事项-2021-10-03(C).pdf

    * 第4题:最后一道题绝对是压轴题,要么是剪枝的搜索,要么是动态规划,甚至还有状压DP、树形DP之类的 学习CSP-J和CSP-S需要系统地进行相关知识的学习,坚持每周做题,集中强化训练,学习重要知识点,掌握程序思想...

    NOI图论大全.pptx

    例如,[CF708C] Centroids问题,通过树形DP和两遍DFS解决成为重心的问题。[BZOJ4878]挑战NP-Hard问题,通过DFS树解决染色问题或寻找简单路径。最短路算法是图论中的重要部分,包括Dijkstra、SPFA和Floyd算法,它们在...

    AcWing算法基础课模板大全

    **树形DP**:用于解决树结构上的动态规划问题。 **记忆化搜索**:在分治或递归策略中,通过保存子问题的结果来避免重复计算,提高效率。 **贪心**:在每一步选择局部最优解,期望达到全局最优。 通过学习以上知识...

    一些简单的算法

    2. **深度优先搜索(DFS)**:在解决迷宫问题或树形结构的游戏中,深度优先搜索是一种常见的方法。它沿着一条路径一直探索到尽头,然后回溯到前一个节点,再尝试另一条路径。在寻找游戏中的所有可能解决方案时,DFS...

    ACM学习资料汇总,ACMer要试试哦!

    - [题目5](http://acm.pku.edu.cn/JudgeOnline/problem?id=1848) —— 树形DP,参考《算法艺术与信息学竞赛》中的树状模型部分。 - [题目6](http://acm.zju.edu.cn/show_problem.php?pid=1234) - [题目7]...

Global site tag (gtag.js) - Google Analytics