qnickx's blog

循此苦旅,直抵群星


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

  • 搜索

P1040 加分二叉树 题解

发表于 2019-10-25 分类于 OI , 题解 阅读次数:

题目链接

传送门

题目描述

设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第ii个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree*本身)的加分计算方法如下:

subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数。

若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;

(1)tree的最高加分

(2)tree的前序遍历

输入格式

第1行:1个整数n(n<30),为节点个数。

第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。

输出格式

第1行:1个整数,为最高加分($ans \leq 4,000,000,000$)。

第2行:n个用空格隔开的整数,为该树的前序遍历。

思路

区间dp,要求前序遍历得首先把一个区间的根给他找出来……转移的同时记录一个区间的根,根据中序遍历的性质,那么对于任意一个区间$[l,r]$,其根为$root$,那么$[l,root-1]$为左子树,$[root+1,r]$为右子树,那么dp方程和遍历顺序都得到了确定:设$dp_{l,r}$为区间$[l,r]$构成树的最大加分,那么$dp_{l,r}=max(dp_{l,root-1}+dp_{root+1,r})$,其中root为枚举的根,跟着一起转移就好了。

最后递归输出就好。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <climits>
#include <cstring>
using namespace std;
typedef long long ll;
int n,root[30][30],dp[30][30];
inline void solve(int l,int r){
if(l>r) return;
printf("%d ",root[l][r]);
if(l==r) return;
solve(l,root[l][r]-1);
solve(root[l][r]+1,r);
}
int main(){
scanf("%d",&n);
for(register int i=1;i<=n;i++) scanf("%d",&dp[i][i]),root[i][i]=i;
for(register int siz=2;siz<=n;siz++){
for(register int l=1;l+siz-1<=n;l++){
int r=l+siz-1;
dp[l][r]=dp[l+1][r]+dp[l][l],root[l][r]=l;//根为l
for(register int k=l+1;k<=r;k++){
if(dp[l][r]<dp[l][k-1]*dp[k+1][r]+dp[k][k]){
dp[l][r]=dp[l][k-1]*dp[k+1][r]+dp[k][k],root[l][r]=k;
}
}
}
}
printf("%d\n",dp[1][n]);
solve(1,n);
return 0;
}
# 区间dp
P5590&&CF241E 赛车游戏 题解
P1312 mayan游戏
  • 文章目录
  • 站点概览
qnickx

qnickx

52 日志
5 分类
49 标签
GitHub E-Mail Google
Links
  • 友链页面
  1. 1. 题目链接
  2. 2. 题目描述
  3. 3. 输入格式
  4. 4. 输出格式
  5. 5. 思路
  6. 6. 代码
© 2021 qnickx
由 Hexo 强力驱动 v3.9.0
|
主题 – NexT.Pisces v7.3.0
|
0%