SJTU 1077 加分二叉树
http://acm.sjtu.edu.cn/OnlineJudge/problem/1077
题意：
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3…,n为节点编号。
每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
分析：
1.题目中明确要求生成的树其中序遍历为1,2,3....n，根据这个我们可以知晓对于a1,a2,a3,a4...ai....an来说，若ai为根，则a1,a2....ai-1在为ai的左子树，ai+1....an为ai的右子树，所以这给我们进行区间动态规划成为了可能
2.区间动态规划，用递归进行书写简单且易于理解
3.路径的记忆，定义一个路径数组，若更新dp值得时候，也更新路径的根节点
4.路径打印，由于要求前序遍历，所以先输出，再分别递归左子树，右子树
5.错误点：在书写代码的时候，DFS（x,i-1）*DFS(i+1,y)，书写太粗心写漏了一个DFS，导致debug了很久都没有找出错误来。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
const int INF=0x7fffffff;
const int MN=50;
LL dp[MN][MN];
int path[MN][MN];
int num[MN];
int n;
int flag;
LL DFS(int x,int y)
{
if(x>y)
{
path[x][y]=0;
return dp[x][y]=1;
}
if(dp[x][y]!=-1) return dp[x][y];
if(x==y)
{
path[x][y]=x;
return dp[x][x]=num[x];
}
dp[x][y]=0;
for(int i=x; i<=y; i++)
{
DFS(x,i-1);
DFS(i+1,y);
if(dp[x][i-1]*dp[i+1][y]+num[i]>dp[x][y])
{
dp[x][y]=dp[x][i-1]*dp[i+1][y]+num[i];
path[x][y]=i;
}
}
return dp[x][y];
}
void Print(int x,int y)
{
if(x>y) return ;
if(flag) printf(" ");
flag=1;
printf("%d",path[x][y]);
Print(x,path[x][y]-1);
Print(path[x][y]+1,y);
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
flag=0;
memset(dp,-1,sizeof(dp));
for(i=1; i<=n; i++)
scanf("%d",&num[i]);
DFS(1,n);
printf("%lld\n",dp[1][n]);
Print(1,n);
printf("\n");
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013-09-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读