网站开发语言手册,前端开发网页设计,网站自定义模块,在哪儿可以找到网站开发的需求加分二叉树
ssl 1033
luogu 1040
题目大意#xff1a;
有一棵中序遍历为1,2,3…n的二叉树#xff08;当然二叉树的样子没有固定#xff09;#xff0c;现在给出每个节点的分数#xff0c;一个节点的加数两个子节点的加数相乘当前节点的分数#xff08;空的子节点加数…加分二叉树
ssl 1033
luogu 1040
题目大意
有一棵中序遍历为1,2,3…n的二叉树当然二叉树的样子没有固定现在给出每个节点的分数一个节点的加数两个子节点的加数相乘当前节点的分数空的子节点加数为1叶子节点加数为它的分数现在要你求最大的加数
输入样例
5
5 7 1 2 10输出样例
145
3 1 2 4 5数据范围
n30n30n30 Ans⩽4,000,000,000Ans \leqslant 4,000,000,000Ans⩽4,000,000,000
解题思路
设f[i][j]f[i][j]f[i][j]为中序遍历为i~j的子树的最大加数然后每次枚举中间点去划分树然后DP即可
代码
#includecstdio
#define max(a,b) (a)(b)?(a):(b)
using namespace std;
long long n,a[50],f[50][50],s[50][50];
void dg(long long l,long long r)//递归输出前序遍历
{if (lr) return;printf(%lld ,s[l][r]);dg(l,s[l][r]-1);dg(s[l][r]1,r);
}
int main()
{scanf(%lld,n);for(int i1;in;i){f[i][i-1]1;//处理空子树的情况f[i1][i]1;scanf(%lld,a[i]);f[i][i]a[i];s[i][i]i; }for(int in-1;i0;--i)//倒着枚举可以先做小的再做大的for(int ji1;jn;j)//枚举范围for(int ki;kj;k)//中间点if (f[i][k-1]*f[k1][j]a[k]f[i][j]){f[i][j]f[i][k-1]*f[k1][j]a[k];//DPs[i][j]k;}printf(%lld\n,f[1][n]);dg(1,n);
}
