当前位置: 首页 > ai >正文

P2014 [CTSC1997] 选课

题目

P2014 [CTSC1997] 选课

算法标签: 动态规划, 树上 d p dp dp

思路

非常显而易见的树上 d p dp dp问题, 可以考虑状态表示 f [ u ] [ j ] f[u][j] f[u][j]代表以 u u u为根节点的子树 分配 j j j个节点的最大价值

树形 d p dp dp解法代码

在递归之前先使用父节点更新当前节点信息, 在递归之后使用子节点更新父节点信息, 这样统计的信息是全面的

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 310, M = N << 1;int n, m;
int head[N], ed[M], ne[M], idx;
int w[N];
int f[N][M];void add(int u, int v) {ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}void dfs(int u, int cnt) {if (cnt <= 0) return;for (int i = head[u]; ~i; i = ne[i]) {int v = ed[i];for (int k = 0; k < cnt; ++k) f[v][k] = f[u][k] + w[v];dfs(v, cnt - 1);for (int k = 1; k <= cnt; ++k) f[u][k] = max(f[u][k], f[v][k - 1]);}
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m;for (int i = 1; i <= n; ++i) {int fa;cin >> fa >> w[i];if (fa) add(fa, i);else add(0, i);}dfs(0, m);int ans = f[0][m];cout << ans << "\n";return 0;
}

树上背包问题解法代码

定义状态表示 f [ u ] [ i ] [ j ] f[u][i][j] f[u][i][j]表示以 u u u为根节点的子树中考虑 i i i个子节点并且总的体积不超过 j j j的所有方案中, 价值最大的方案, 因为是 d f s dfs dfs进行状态转移, 可以像 01 01 01背包问题一样优化掉一维, 但是第二维的体积需要反向枚举

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 310, M = N << 1;int n, m;
int head[N], ed[M], ne[M], idx;
int f[N][M];void add(int u, int v) {ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}void dfs(int u) {for (int i = head[u]; ~i; i = ne[i]) {int v = ed[i];dfs(v);for (int j = m; j >= 0; --j) {for (int k = 0; k < j; ++k) {f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);}}}
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m;m++;for (int i = 1; i <= n; ++i) {int fa;cin >> fa >> f[i][1];add(fa, i);}dfs(0);int ans = f[0][m];cout << ans << "\n";return 0;
}
http://www.xdnf.cn/news/9404.html

相关文章:

  • 53、用例(Use Case)详解
  • 封装索引列表
  • AXI3、AXI4 和 AXI5 的详细差异对比
  • 第三章、运动学逆解(双足轮根据腿高求舵机角度)
  • 完全卸载VS Code--Windows版
  • 在 Vue + Vite 项目中,直接使用相对路径或绝对路径引用本地图片资源时,图片无法正确显示。
  • Claude 4对比Claude 3.7全面评测:2025最新AI模型实测对比
  • 山东大学软件学院创新项目实训开发日志——第十三周
  • xilinx 7系列底层可配置逻辑块CLB中的LUT、FF等资源
  • IT编程学习资料大全​​​​​​​​
  • 嵌入式学习之系统编程(六)线程
  • 打破边界 智启新篇 新一代质检LIMS系统的演进蓝图
  • QGis实现geoserver上的样式展示(方便样式编辑)
  • ShardingSphere-读写分离
  • leetcode0611. 有效三角形的个数-medium
  • ROS2学习(14)------ ROS2Launch 多节点启动与配置脚本
  • 基于stm32的 永磁同步电机二电平驱动控制系统设计
  • OpenKylin文件管理器界面层级切换问题
  • 多相电机驱动控制学习(1)——基于双dq坐标系的六相/双三相PMSM驱动控制
  • ABC 377
  • 互联网医疗问诊APP原型设计:12个实战案例解析
  • Workflow
  • 如何合理选择智能外呼机器人:多维评估
  • SAP-ABAP:SAP的DMS根据物料号获取附件详解
  • 网络通信的基石:深入理解帧与报文
  • [BUG记录]0X10 会话切换服务响应NRC 0x10
  • <<运算符重载 和 c_str() 的区别和联系
  • TF 卡和 NM 卡有何区别?
  • openinstall支持豆瓣广告监测,赋能品牌深挖社交流量
  • Baklib知识中台体系构建与应用解析