洛谷 P1040 NOIP 2003 提高组 加分二叉树

url: https://www.luogu.com.cn/problem/P1040

tag:
动态规划,递归,枚举,区间DP,NOIP提高组,2003

思路:
使用区间dp的思路,令 f[i][j] 为节点i到节点j之间最大的加分,并用 root[i][j] 记录下这段区间的根节点。之后遍历每一种可能的区间,依据题目的公式更新数组f记录root最后得出结果输出 f[1][n] 即表示给定的二叉树tree的最高加分。然后再输出该情况时树的前序遍历即可。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. typedef long long LL;
  7. const int N = 31;
  8. int h[N], e[N * 2], ne[N * 2], idx;
  9. int n;
  10. LL f[N][N];
  11. int root[N][N];
  12. void print(int l ,int r)
  13. {
  14. if (l > r) return;
  15. cout << root[l][r] << ' ';
  16. if (l == r) return;
  17. print(l, root[l][r] - 1),print(root[l][r] + 1, r);
  18. }
  19. int main()
  20. {
  21. cin >> n;
  22. for (int i = 1; i <= n; i ++) cin >> f[i][i], root[i][i] = i;
  23. for (int len = 1; len <= n; len ++)
  24. for (int i = 1; i + len <= n; i ++)
  25. {
  26. int j = i + len;
  27. f[i][j] = f[i + 1][j] + f[i][i];
  28. root[i][j] = i;
  29. for (int k = i + 1; k <= j; k ++)
  30. {
  31. if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k])
  32. {
  33. f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
  34. root[i][j] = k;
  35. }
  36. }
  37. }
  38. cout << f[1][n] << endl;
  39. print(1, n);
  40. return 0;
  41. }
添加新评论