设一个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行:一个整数n(n<30),为节点个数。
第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。
第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。
第2行:n个用空格隔开的整数,为该树的前序遍历。
-----------------------------------------------------
这道题是从RQNOJ上找来的。应该是一道比较经典的树形DP了。
用dp[i][j]表示从i到j的子树所得的最大分值,pos[i][j]表示从i到j的子树的根的序号
然后就是递归求解了,类似于记忆化搜索吧。从叶子结点向根部进行DP。
最后输出的时候按照先序遍历输出即可
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include<iostream>
#include<vector>
#include <list>
#include <map>
#include <set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include <map>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#define MAXN 10005
#define INF1000000000
#define eps 1e-7
#define L(x)x<<1
#define R(x)x<<1|1
using namespace std;
long long dp[33][33];
int pos[33][33], n;
long long num[33];
long long find(int s,int t)
{
if(s > t) return 1;
if(s == t) return num[s];
if(dp[s][t]) return dp[s][t];
long long mx = 0;
for(int i = s; i <= t; i++)
{
long long tmp = find(s, i - 1) * find(i+ 1, t) + num[i];
if(tmp > mx)
{
mx = tmp;
pos[s][t] = i;
}
}
dp[s][t] = mx;
return dp[s][t];
}
void output(int s,int t, int k)
{
if(s > t) return;
if(s == t) {printf(" %d", s);return;}
if(k) printf(" ");
printf("%d", pos[s][t]);
output(s, pos[s][t] - 1, 1);
output(pos[s][t] + 1, t, 1);
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%I64d", &num[i]);
printf("%I64d\n", find(1, n));
output(1, n, 0);
printf("\n");
return 0;
}
HDU 1520
使用了父子兄弟表示法
又一次明显的展示了DP的最优子结构的特性
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10007
#define INF 1000000000
#define eps 1e-7
using namespace std;
struct node
{
int brother, child, father;
int yes, no;
int mx()
{
return yes > no ? yes : no;
}
void init()
{
brother = child = father = no = 0;
}
} tree[MAXN];
int n;
void dfs(int idx)
{
int child = tree[idx].child;
while(child)
{
dfs(child);
tree[idx].yes += tree[child].no;
tree[idx].no += tree[child].mx();
child = tree[child].brother;
}
}
int main()
{
while(scanf("%d", &n) != EOF)
{
for(int i = 1; i <= n; i++)
{
scanf("%d", &tree[i].yes);
tree[i].init();
}
int x, y;
while(scanf("%d%d", &x, &y) != EOF)
{
if(x == 0 && y == 0) break;
tree[x].father = y;
tree[x].brother = tree[y].child;
tree[y].child = x;
}
for(int i = 1; i <= n; i++)
{
if(!tree[i].father)
{
dfs(i);
printf("%d\n", tree[i].mx());
break;
}
}
}
return 0;
}
分享到:
相关推荐
数据结构 二叉树 树形输出 数据结构 二叉树 树形输出 数据结构 二叉树 树形输出
二叉树树形输出源码,可以得到二叉树的树形结构
打印二叉树-按照二叉树的形状打印 用C++实现,运行成功
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作: (1)访问结点本身(N), (2)遍历该结点的左子树(L), (3)遍历该...
算法-树形结构- 树与二叉树- 树的数据生成器.rar
树和二叉树 树和二叉树 树和二叉树 树和二叉树树和二叉树树和二叉树
数据结构树和二叉树遍历二叉树和线索二叉树PPT学习教案.pptx
算法-树形结构- 树与二叉树.rar
简单的实现了树与二叉树的转换功能!很实用
算法-树形结构- 树与二叉树- 树的重心.rar
算法-树形结构- 树与二叉树- 无根树转有根树.rar
两种序输入二叉树,恢复该二叉树并打印出树形
算法-树形结构- 树与二叉树- 树的直径.rar
算法-树形结构- 树与二叉树- 树的中心.rar
树和二叉树课件,主要内容有树的逻辑结构;树的存储结构;二叉树的逻辑结构;二叉树的存储结构及实现;树、森林与二叉树的转换;哈夫曼树
二叉树的生成,先序,中序,后续遍历,以及树形输出,很实用哦,这个是C语言版的
详细的树和二叉树的教程,还附有源代码 部分代码如下: 二叉树头文件.h //二叉树的二叉链表存储表示 typedef struct BiTNode {TElemType data; //二叉树结点数据域 struct BiTNode *lchild,*rchild; //左右孩子指针...
输入共3行:第一行为满二叉树中结点个数n(n<1024);第二行为n个整数,表示二叉树的先序遍历序列;第三行也有n个整数,表示二叉树的中序遍历序列。整数间以空格分割。
根据括号表达式构造二叉树,对二叉树进行前序,中序,后序,层序遍历,并用树形方式打印输出,有详细注释,供C++数据结构课程学习与交流使用。
树与二叉树_习题树与二叉树_习题树与二叉树_习题