今天学习了树形 dp, 确实, 感受到了深深的压力... 一会还得去写选课那道题
先看题目:
首先我们看到关键字: 中序遍历既然已经给出我们分数的算法, 所以我们就可以通过枚举根节点来解决问题在每一个根节点下求最优解, 且记录下每一个根节点, 就恰好能完成两个任务即我们需要写两个子程序
看代码:(请勿直接复制粘贴)
- #include < stdio.h > int n,
- point[32],
- f[32][32],
- mumber[32][32];
- long long tree(int left, int right) {
- if (left > right) return 1; // 题目中有提到, 如果 left>right 即是一个空树, 加分为 1
- if (left == right) return point[left]; // 即为根节点, 就加上该点的分数
- if (f[left][right]) return f[left][right]; // 记忆化搜索, 如果没有记忆化很可能会 TLE 上几个点
- long long MAX = 0,
- maxnow = 0; // 定初值
- int kkk = 0;
- for (int k = left; k <= right; k++) // 枚举根节点
- {
- maxnow = point[k] + tree(left, k - 1) * tree(k + 1, right); // 计算当前根节点下的分数的最优解
- if (maxnow > MAX) {
- MAX = maxnow; // 打擂台
- kkk = k; // 记录此时的根节点
- }
- f[left][right] = MAX;
- mumber[left][right] = kkk;
- }
- return MAX; // 返回最大值, 第一个问题解决
- }
- void print(int l, int r) {
- if (l > r) return; // 终止条件
- if (l == r) {
- printf("%d", l); // 根节点
- return;
- }
- int kkk = mumber[l][r];
- printf("%lld", kkk); // 输出该节点的编号
- print(l, kkk - 1); //
- print(kkk + 1, r); // 前序遍历
- }
- int main() {
- scanf("%d", &n);
- for (int i = 1; i <= n; i++) scanf("%d", &point[i]); // 读入分数
- printf("%d\n", tree(1, n)); // 输出最优解 (返回的值)
- print(1, n);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2497109.html