洛谷P1040 加分二叉树

Bertha 。 2022-05-31 13:16 115阅读 0赞

## 题目描述 ##

设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为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个用空格隔开的整数，为该树的前序遍历。

![70][]

没错我很菜。本大二狗看到二叉树上来就用指针写了建立二叉树数的函数，删除节点的函数，前序遍历的函数，你没看错，我用的就是指针。结果TLE只得了20分。一点优化都没写。

20分代码（指针版，奇慢无比，但应该是对的）

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<string.h>
    using namespace std;
    
    int node[35];
    bool flag[35];//判断某个序号是否用过
    int anss[35];//存储最后的答案
    int n;
    int ans = 0;
    struct Btree
    {
    	struct Btree *left;
    	struct Btree *right;
    	int score;
    	int addScore;
    	int mark;
    };
    Btree* T=NULL;
    Btree* insertNode(Btree * T,int num)
    {
    	if (T == NULL)
    	{
    		T = (Btree*)malloc(sizeof(struct Btree));
    		T->left = NULL;
    		T->right = NULL;
    		T->mark = num;
    		T->score = node[num];
    		T->addScore = 0;
    	}
    	else
    	{
    			if (num < T->mark)
    				T->left = insertNode(T->left, num);
    			else
    				T->right = insertNode(T->right, num);
    		
    	}
    	return T;
    }
    int j=1;//anss数组的下标从1开始
    //前序遍历
    void pre(Btree* T) 
    {
    	if (T)
    	{
    		//printf("%d ", T->mark);
    		anss[j++] = T->mark;
    		pre(T->left);
    		pre(T->right);
    	}
    }
    //删除序号num为的节点
    Btree *Del(Btree* t,int num)
    {
    	if (t->mark == num)
    	{
    		free(t);
    		return NULL;
    	}
    	else
    	{
    
    		if (num < t->mark)
    			t->left = Del(t->left, num);
    		else
    			t->right = Del(t->right, num);
    	}
    	return t;
    }
    //计算每个节点的加分
    int count(Btree* T)
    {
    	if (T==NULL)
    	{
    		return 1;
    	}
    	else
    	{
    			if (T->left&&T->right)
    				T->addScore = T->score + count(T->left)*count(T->right);
    			else if (T->left&&!T->right)
    				T->addScore = T->score + count(T->left);
    			else if (T->right&&!T->left)
    				T->addScore = T->score + count(T->right);
    			else
    				T->addScore = T->score;
    	}
    	return T->addScore;
    }
    //搜索每个节点,
    void dfs(int num)
    {
    	if (num == n)
    	{
    		int tmp = count(T);
    		//cout << tmp << '\n';
    		if (ans < tmp)
    		{
    			ans = tmp;
    			j = 1;
    			pre(T);
    		}
    	}
    	for (int i = 1; i <= n; i++)
    	{
    		if (flag[i]) continue;
    		flag[i] = 1;
    		T=insertNode(T, i);
    		dfs(num + 1);
    		flag[i] = 0;
    		T=Del(T, i);
    	}
    }
    
    
    
    int main()
    {
    	freopen("1.txt", "r", stdin);
    	
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    		cin >> node[i];
    	dfs(0);
    	cout << ans << '\n';
    	for (int i = 1; i < j; i++)
    		cout << anss[i]<<' ';
    	return 0;
    }

看了题解知道有区间dp这个东西，真是感到自己的无知，但是学习了。

参考题解：[http://blog.csdn.net/JYL1159131237/article/details/78355042][http_blog.csdn.net_JYL1159131237_article_details_78355042]

用区间动规的模型解决掉：直接定义一个f\[i\]\[j\]表示从i到j的最大值，则

f\[i\]\[j\]=max(f\[i\]\[k-1\]\*f\[k+1\]\[j\]+f\[k\]\[k\])

枚举k即可。

接下来是如何建树的问题，只有把树建好了，才能输出其前序遍历。于是，我们看到了两个关键词：二叉树，中序遍历。有了这两个关键词，加上区间动规，这棵树就能建起来了。根据二叉树的特性来建树。所以这颗树的前序遍历，只需要边动规边记录下root\[i\]\[j\]=k表示i到j的根为k即可确定树的构造。

过了的代码

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<string.h>
    using namespace std;
    
    int root[32][32];//root[a][b]表示a,b区间里父节点的编号。
    int f[32][32]; //f[i][j]表示从i到j的最大值
    int n;
    
    int count(int left,int right)
    {
    	if (left > right)
    		return 1;
    	if (f[left][right] == 0)
    	{
    		for (int i = left; i <= right; i++)
    		{
    			int tmp = f[left][right];
    			f[left][right] = max(count(left, i - 1) * count(i + 1, right) + f[i][i], f[left][right]);
    			if (tmp < f[left][right])
    			{
    				root[left][right] = i;
    			}
    		}
    	}
    	return f[left][right];
    }
    
    void print(int left,int right)
    {
    	if (left > right)
    		return;
    	else
    	{
    		cout << root[left][right] << ' ';
    		print(left, root[left][right] - 1);
    		print(root[left][right] + 1, right);
    	}
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> f[i][i];
    		root[i][i] = i;
    	}
    
    	cout << count(1, n) << '\n';
    	print(1, n);
    
    	return 0;
    }

这就是用了算法和美用算法的差距，短了一半竟然。

坚信越努力，越幸运。

[70]: /images/20220531/b3bdd84b0c014b4ab12345df4a1971da.png
[http_blog.csdn.net_JYL1159131237_article_details_78355042]: http://blog.csdn.net/JYL1159131237/article/details/78355042