网站开发后是不是下挂到域名,网页设计基础实训,海口官网设计公司,网页设计公司找哪家试题链接#xff1a; 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 131072K#xff0c;其他语言262144K
64bit IO Format: %lld题目描述 设一个n个节点的二叉树tree的中序遍历为#xff0…试题链接
文章目录题目描述题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 131072K其他语言262144K
64bit IO Format: %lld题目描述 设一个n个节点的二叉树tree的中序遍历为l,2,3,…,n其中数字1,2,3,…,n为节点编号。每个节点都有一个分数均为正整数记第j个节点的分数为ditree及它的每个子树都有一个加分任一棵子树subtree也包含tree本身的加分计算方法如下subtree的左子树的加分× subtree的右子树的加分subtree的根的分数若某个子树为主规定其加分为1叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为1,2,3,…,n且加分最高的二叉树tree。 要求输出
1tree的最高加分
2tree的前序遍历输入描述: 第1行一个整数nn30为节点个数。 第2行n个用空格隔开的整数为每个节点的分数分数100。 输出描述: 第1行一个整数为最高加分结果不会超过4,000,000,000。 第2行n个用空格隔开的整数为该树的前序遍历。 示例1 输入
5
5 7 1 2 10输出
145
3 1 2 4 5题解
这个题没大看明白。。。 样例分析一阵子也没算出145我太菜了 更新 看了其他题解后逐渐明白一点 记忆化搜索
f [ l ] [ r ] 表示这颗树中序遍历中第l个节点到第r个节点为一颗子树的得分最大值 中序遍历中根的左边就是左子树右边就是右子树对每一颗子树枚举根节点k为位置左子树的编号都小于根节点右子树都大于根节点 枚举根k左子树l…k-1 右子树 k1…r 区间为连续的直接使用f [ i ] [ k-1 ] 与 f [ k1 ] [ j ]两者相乘就行
f [ i ] [ j ] max ( f [ i ] [ k-1 ] * f [ k1 ] [ j ] tree [ k ]) f [ i ] [ k-1 ] 表示左节点 f [ k1 ] [ j ]表示右节点
我们再用一个根节点数组root [ i ][ j ] 表示区间i到j选择的根节点是什么
边界为k i或者k j的时候的情况。
代码
#includebits/stdc.h
using namespace std;
#define int long long
const int maxn31;
int tree[maxn],f[maxn][maxn],n;
inline void dfs(int l,int r){if(lr)return;if(lr){printf(%d ,l);return;}for(int il;ir;i){if(f[l][r]f[l][i-1]*f[i1][r]tree[i]){couti ; dfs(l,i-1);dfs(i1,r);return;}}
}
inline void dfs1(){f[n1][n]1;for(int in;i;--i){for(int ji1;jn;j){for(int ki;kj;k){f[i][j]max(f[i][j],f[i][k-1]*f[k1][j]tree[k]);}}}coutf[1][n]endl;
}
int main(){cinn;for(int i1;in;i){cintree[i];f[i][i]tree[i];f[i][i-1]1;}dfs1();dfs(1,n);return 0;
}
