本文主要是介绍洛谷P1040-加分二叉树-dp+二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
P1040-加分二叉树
这道题放在深度优先搜索的训练题中，可是我实在没有看出来应该怎么搜索。看了题解以后才看出来是一个很简单的dp(我果然还是太菜了)
看出dp并且算出来最大的分数不是很复杂，关键是输出给定中序遍历序列的二叉树的先序遍历，要用一个数组保存在dp的时候确定的根节点，觉得不是很容易想到。
AC代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;typedef long long ll;
const int MAXN=35;
int n,first=1;
int father[MAXN][MAXN];
ll score[MAXN][MAXN];ll search(int l,int r)
{ll tmp;if(l>r) return 1; //如果l>r说明没有子树，应该为1，乘起来以后就变成了只有左子树或者右子树//不用考虑叶子节点，因为叶子节点的分数是它本身，所以不会进行dpif(score[l][r]==-1){for(int k=l;k<=r;k++){tmp=search(l,k-1)*search(k+1,r)+score[k][k];if(tmp>score[l][r]){score[l][r]=tmp;father[l][r]=k; //保存这一段的根节点}}}return score[l][r];
}
void print(int l,int r)
{if(l>r) return;if(first)first=0;elseprintf(" ");printf("%d",father[l][r]);print(l,father[l][r]-1);print(father[l][r]+1,r);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&score[i][i]);father[i][i]=i;for(int j=i+1;j<=n;j++){score[i][j]=-1;}}printf("%lld\n",search(1,n));print(1,n);return 0;
}
这篇关于洛谷P1040-加分二叉树-dp+二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
