题意：你有n门课程，你可以选择m门课选修，有的课程有先修课，每一门课程都有学分，求你可获得的最大学分为多少？ 思路：树状dp没先修课的与0节点连接，有先修课的与先修课连接，这样就是0节点为根的一棵树了。dp[i][j]表示以i节点为根的子树且选择了i时共选择j门课程的最大学分，这样就满足了先修课的条
展开全文
前言 清楚姐姐树形题单的最后一题了... 思路 考虑先当前节点必须把当前节点前面连接到根的节点全部选了..那么我们不妨令为选了节点且选取数量为的一个最大价值.那么转移似乎挺简单的. 代码 #include <bits/stdc++.h>
using namespace std;
cons
展开全文
树形dp模板题首先建一个虚拟节点0，让原本的森林变成一颗树。然后我们设dp[i][j]表示以i为根的子树中,选j门课的最大价值。转移时我们枚举当前以x为根的子树选课的数量(t)，以及分配给x的子节点y多少节课(j)。不难写出方程：dp[x][t]=max(dp[x][t],dp[x][t-j]+dp
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
