树形 dp 大概是在树上的 dp, 可以有一些父亲节点和儿子节点的关系来 dp
一道经典例题:
没有上司的舞会
Ural 大学有 N 个职员, 编号为 1-N 他们有从属关系, 也就是说他们
的关系就像一棵以校长为根的树, 父结点就是子结点的直接上司每
个职员有一个快乐指数现在有个周年庆宴会, 要求与会职员的快乐
指数最大但是, 没有职员愿和直接上司一起与会
tyvj1052
简单来讲就是某个职员的直接上司参加, 这些职员都不会参加, 发现上司和职员的关系像一颗树, 可以先思考方程
少女祈祷中......
dp[i][1/0]表示 i 节点这个人来或不来时所能达到的最大欢乐指数; 则 max(dp[root][0/1])就是答案;
则可以写出方程
- dp[i][1]+=max(dp[son[i]][0]),
- dp[i][0]+=max(dp[son[i][1],dp[son[i]][0]);
则代码如下
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- int n;
- int ri[6010],root;
- int f[6010][2];
- struct data
- {
- int v,nxt;
- }edge[6010];
- int cnt,alist[6010];
- void add(int u,int v)// 邻接表存图
- {
- edge[++cnt].v=v;
- edge[cnt].nxt=alist[u];
- alist[u]=cnt;
- }
- int poi[6010];
- void dp(int x)
- {
- f[x][0]=0;
- f[x][1]=ri[x];// 如果 x 来了, 欢乐指数加 x 自己的
- int nxt=alist[x];
- while(nxt)// 遍历儿子
- {
- int son=edge[nxt].v;
- dp(son);
- f[x][0]+=max(f[son][0],f[son][1]);// 刚才的方程
- f[x][1]+=f[son][0];
- nxt=edge[nxt].nxt;
- }
- }
- int main()
- {
- // freopen("in","r",stdin);
- scanf("%d",&n);
- for(int i=1;i<=n;++i)
- {
- scanf("%d",&ri[i]);
- }
- for(int i=1;i<n;++i)
- {
- int u,v;
- scanf("%d%d",&u,&v);// 存图
- add(v,u);
- poi[u]=1;
- }
- for(int i=1;i<=n;++i) // 找到根节点
- {
- if(poi[i]==0)
- {
- root=i;
- break;
- }
- }
- dp(root);
- printf("%d",max(f[root][0],f[root][1]));
- }
然后看一道稍微变式题
luogu p2014 选课
题目描述
在大学里每个学生, 为了达到一定的学分, 必须从很多课程里选择一些课程来学习, 在课程里有些课程必须在某些课程之前学习, 如高等数学总是在其它课程之前学习现在有 N 门功课, 每门课有个学分, 每门课有一门或没有直接先修课 (若课程 a 是课程 b 的先修课即只有学完了课程 a, 才能学习课程 b) 一个学生要从这些课程里选择 M 门课程学习, 问他能获得的最大学分是多少?
输入输出格式
输入格式:
第一行有两个整数 N,M 用空格隔开(1<=N<=300,1<=M<=300)
接下来的 N 行, 第 I+1 行包含两个整数 ki 和 si, ki 表示第 I 门课的直接先修课, si 表示第 I 门课的学分若 ki=0 表示没有直接先修课(1<=ki<=N, 1<=si<=20)
输出格式:
只有一行, 选 M 门课程的最大得分
dp[i][j]表示第 i 个点选 j 个数所获的最大学分, 包括自己;
dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[i][k]);(哈~~~, 好困)
看代码吧
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- int n,m;
- struct data
- {
- int v,nxt;
- }edge[600];
- int cnt,alist[600];
- void add(int u,int v)
- {
- edge[++cnt].v=v;
- edge[cnt].nxt=alist[u];
- alist[u]=cnt;
- }
- int val[310];int f[310][310];
- void dp(int x)
- {
- f[x][1]=val[x];
- // printf("%d\n",nxt);
- for(int i=alist[x];i;i=edge[i].nxt)// 遍历 son 节点
- {
- int son=edge[i].v;
- dp(son);
- for(int j=m+1;j>=1;--j)// 枚举在 x 的 son 中选几个, 倒叙很重要
- {
- for(int k=0;k<j;++k)// 枚举在 son 中选几个
- {
- f[x][j]=max(f[x][j],f[x][j-k]+f[son][k]);
- }
- }
- }
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i)
- {
- int v;
- scanf("%d%d",&v,&val[i]);
- add(v,i);
- }
- dp(0);// 因为没根, 所以建一个总根
- printf("%d",f[0][m+1]);
- }
少女犯困中......
00:13:55
来源: http://www.bubuko.com/infodetail-2506176.html