热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

一些树形DP题目の总结

一、没有上司的舞会题目描述Ural大学有N名职员,编号为1~N。他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数&#

一、没有上司的舞会


题目描述

Ural大学有N名职员,编号为1~N。

他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。

每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。

现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。

在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。

输入格式

第一行一个整数N。

接下来N行,第 i 行表示 i 号职员的快乐指数Hi。

接下来N-1行,每行输入一对整数L, K,表示K是L的直接上司。

输出格式

输出最大的快乐指数。

样例

样例输入

复制7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

样例输出

复制5

数据范围与提示

1≤N≤6000,

−128≤Hi≤127



(1)题目分析

        首先关于树形dp,需要dfs的遍历到叶子节点,更新叶子结点的值再回溯向上步步更新。所以一般再扫到子节点之后先写dfs(v,u),再写转移方程。赋初值在一进入dfs时就进行。而转移方程一般有两类:


       ①选择节点类:
​        f[u][0]=f[u][1], f[u][1]=max/min(f[v][0],f[v][1])


       ②树形背包类:

        f[v][k]=f[u][k]+val, f[u][k]=max(f[u][k],f[v][k-1])

         回归本题,这道题明显用的是第一类选择节点。上司和下属们,只能留一方。


(2)代码实现

#include
#include
using namespace std;
int n,r[6005],head[6005],cnt,root;
int dp[6005][2],ans,in[6005];
struct egde{int to,next;
}e[6005];
inline void add(int u,int v){//链式前向星存图cnt++;e[cnt].next=head[u];e[cnt].to=v;head[u]=cnt;
}
inline void dfs(int u,int fa){dp[u][1]=r[u];//赋初值dp[u][0]=0;for(int i=head[u];i;i=e[i].next){int v=e[i].to;dfs(v,u); //先dfsdp[u][1]+=dp[v][0];dp[u][0]+=max(dp[v][1],dp[v][0]);}ans=max(dp[u][1],dp[u][0]);
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&r[i]);for(int i=1,u,v;i}



二、选课


题目描述

学校实行学分制。

每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。

学校开设了 N 门的选修课程,每个学生可选课程的数量 M 是给定的。

学生选修了这 M 门课并考核通过就能获得相应的学分。

在选修课程中,有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其他的一些课程的基础上才能选修。

例如《Windows程序设计》必须在选修了《Windows操作基础》之后才能选修。

我们称《Windows操作基础》是《Windows程序设计》的先修课。

每门课的直接先修课最多只有一门。

两门课可能存在相同的先修课。

你的任务是为自己确定一个选课方案,使得你能得到的学分最多,并且必须满足先修条件。

假定课程之间不存在时间上的冲突。

输入格式

输入文件的第一行包括两个整数N、M(中间用一个空格隔开)其中1≤N≤300,1≤M≤N。

接下来N行每行代表一门课,课号依次为1,2,…,N。

每行有两个数(用一个空格隔开),第一个数为这门课先修课的课号(若不存在先修课则该项为0),第二个数为这门课的学分。

学分是不超过10的正整数。

输出格式

输出一个整数,表示学分总数。

样例

样例输入

复制7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

样例输出

复制13


(1)题目分析

        首先 这个图是一个“森林”,我们应对这种问题时,不妨设一个总根节点‘0’或是‘n+1’,以此开始。同时这道题是“背包”,但不是分组背包。我们需要利用树形DP的思想,且这道题属于上文提及的类型②树形背包类。我们设dp[i][j]的值表示以i为根节点,剩余可选j节课的可得最大学分。由此推转移公式: f[u][j]=max(f[u][j],f[v][k]+f[u][j-k]) 其中u为根节点,v为子节点。


(2)代码实现

#include
#include
#include
using namespace std;
int N,M,cnt,head[305],in[305],val[305];
int dp[305][305];
struct edge{int to,next;
}e[305];
inline void add(int u,int v){cnt++;e[cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
inline void dfs(int u,int fa){for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==fa)continue;//printf("v=%d\n",v);dfs(v,u);for(int j=M;j>0;j--){// 0/1背包for(int k=j-1;k>=0;k--){dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[v][k]+val[v]);}//printf("dp[%d][%d]=%d\n",u,j,dp[u][j]);}}
}
int main(){scanf("%d%d",&N,&M);for(int i=1,u;i<=N;i++){scanf("%d%d",&u,&val[i]);if(u!=0){add(u,i);}else add(N+1,i);//以‘N+1’为总根} dfs(N+1,-1);printf("%d",dp[N+1][M]);
}



三、皇宫看守


题目描述

太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。

皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状,某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。

帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。

Picture1

输入格式

输入中数据描述一棵树,描述如下:

第一行n,表示树中结点的数目。

第二行至第n+1行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号i,在该宫殿安置侍卫所需的经费k,该边的儿子数m,接下来m个数,分别是这个节点的m个儿子的标号。

对于一个n个结点的树,结点标号在1到n之间,且标号不重复。

输出格式

输出最少的经费

样例

样例输入

复制6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

样例输出

复制25

样例解释

有六个区域被安排的情况如左图所示。

如右图,灰色点安排了警卫,2号警卫可以观察1,2,5,6 ,3号警卫可以观察1,3 ; 4 号警卫可以观察 1,4。

总费用:16+5+4=25

Picture2

Picture3



(1)题目分析

        这道题目就有区别于洛谷的P2016 战略游戏,更有DP的取优思想。对于任意一个点i,它可以被自己的士兵监视,也可以被父亲监视,更可以被儿子监视,明显要三者中取优。我们设dp[i][3],其中二维的‘0’表示i不放士兵,被父亲监视;‘1’表示i不放士兵,被儿子监视;‘2’表示i放士兵。但这之中还有一个细节:当我们决定i被儿子监视,那么i的儿子中必要有一个放了士兵,这该怎么在我们取优时保证呢?我们来看代码。


(2)代码实现

#include
#include
#define Maxn 1505
#define inf 1e9
using namespace std;
int n,m,cos[Maxn],cnt,head[Maxn],in[Maxn];
int dp[Maxn][3];
//dp[i][0]-->i不放士兵,被父亲监视
//dp[i][1]-->i不放士兵,被儿子监视
//dp[i][2]-->i放士兵
struct egde{int to,next;
}e[Maxn*2];
inline void add(int u,int v){cnt++;e[cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
inline void dfs(int u,int fa){int d=inf;dp[u][2]=cos[u];for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==fa) continue;//printf("v=%d\n",v);dfs(v,u);dp[u][0]+=min(dp[v][2],dp[v][1]);dp[u][1]+=min(dp[v][2],dp[v][1]);d=min(d,dp[v][2]-min(dp[v][2],dp[v][1]));//特别注意,选一个dp[v][2]与dp[v][1]相差最小的,保证在这种情况下至少有一个儿子放了士兵dp[u][2]+=min(dp[v][2],min(dp[v][1],dp[v][0]));//printf("dp[%d][1]=%d dp[%d][0]=%d\n",v,dp[v][1],v,dp[v][0]); }dp[u][1]+=d;//补上差价//printf("tot=%d cnt=%d\n",tot,cnt);//printf("u=%d dp[%d][1]=%d dp[%d][0]=%d\n",u,u,dp[u][1],u,dp[u][0]);
}
int main(){scanf("%d",&n);//printf("%d\n",n);for(int i=1,u,k;i<=n;i++){scanf("%d%d%d",&u,&k,&m);//printf("%d %d %d ",u,k,m);cos[u]=k;for(int j=1,v;j<=m;j++){scanf("%d",&v);//printf("%d ",v);add(u,v);in[v]++;}//printf("\n");}for(int i=1;i<=n;i++){if(in[i]==0){dfs(i,0);printf("%d",min(dp[i][2],dp[i][1]));break;}}return 0;
}


注:本文章为个人学习总结,如有错误或不当之处,还望批评指正啊( ̄︶ ̄)↗ 


推荐阅读
  • 本文详细探讨了HihoCoder平台上的1398号问题——最大权闭合子图的求解方法。通过具体实例,深入分析了最大权闭合子图的概念及其算法实现。 ... [详细]
  • 网络流24题——试题库问题
    题目描述:假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]
  • hlg_oj_1116_选美大赛这题是最长子序列,然后再求出路径就可以了。开始写的比较乱,用数组什么的,后来用了指针就好办了。现在把代码贴 ... [详细]
  • 洛谷 P4009 汽车加油行驶问题 解析
    探讨了经典算法题目——汽车加油行驶问题,通过网络流和费用流的视角,深入解析了该问题的解决方案。本文将详细阐述如何利用最短路径算法解决这一问题,并提供详细的代码实现。 ... [详细]
  • 编程解析:CF989C 花朵之雾 (构造算法)
    本文深入探讨了CF989C '花朵之雾'问题的构造算法,提供了详细的解题思路和代码实现。 ... [详细]
  • 编码unicode解决了语言不通的问题.但是.unicode又有一个新问题.由于unicode是万国码.把所有国家的文字都编进去了.这就导致一个unicode占用的空间会很大.原来 ... [详细]
  • 想把一组chara[4096]的数组拷贝到shortb[6][256]中,尝试过用循环移位的方式,还用中间变量shortc[2048]的方式。得出的结论:1.移位方式效率最低2. ... [详细]
  • 本文详细介绍了Linux系统中信号量的相关函数,包括sem_init、sem_wait、sem_post和sem_destroy,解释了它们的功能和使用方法,并提供了示例代码。 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 本文详细介绍了 `org.apache.tinkerpop.gremlin.structure.VertexProperty` 类中的 `key()` 方法,并提供了多个实际应用的代码示例。通过这些示例,读者可以更好地理解该方法在图数据库操作中的具体用途。 ... [详细]
  • 本文通过C++语言实现了一个递归算法,用于解析并计算数学表达式的值。该算法能够处理加法、减法、乘法和除法操作。 ... [详细]
  • 问题描述现在,不管开发一个多大的系统(至少我现在的部门是这样的),都会带一个日志功能;在实际开发过程中 ... [详细]
  • 本问题涉及在给定的无向图中寻找一个至少包含三个节点的环,该环上的节点不重复,并且环上所有边的长度之和最小。目标是找到并输出这个最小环的具体方案。 ... [详细]
  • 本文深入探讨了Go语言中的接口型函数,通过实例分析其灵活性和强大功能,帮助开发者更好地理解和运用这一特性。 ... [详细]
  • spring boot使用jetty无法启动 ... [详细]
author-avatar
Shaw
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有