洛谷P1040 加分二叉树

题目描述

设一个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个用空格隔开的整数，为该树的前序遍历。

输入输出样例

输入样例#1：

5
5 7 1 2 10

输出样例#1：

145
3 1 2 4 5

由于题目给的是中序遍历，也就是先左后根在右（一开始想成了前序遍历（雾））。那么连续的点显然是递归的一棵子树。我们可以定义dp[i][j]表示i, j组成的子树的最大加分。咦？不就变成区间dp了吗？

轻松愉快写状态转移：dp[l][r] = dp[l][k - 1] * dp[k + 1][r] + w[k] 枚举k:l ~ r。

然而这道题最棘手的地方不在于dp部分，而在于输出前序遍历。考虑记录dp过程。可以用s[l][r]表示l,r这棵子树最大的加分时要选s[l][r]，这样我们就可以写一个伪树遍历硬搞过去了。（另外听说要用longlong？？反正没用也过了=W=）代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 35;
unsigned int dp[maxn][maxn];
int n, w[maxn], s[maxn][maxn], l, r;
void dfs(int l, int r) {
	if(l > r)	return;
	printf("%d ", s[l][r]);
	if(l == r)  return;
	dfs(l, s[l][r] - 1), dfs(s[l][r] + 1, r);
}
signed main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i) 
        scanf("%d", &w[i]), dp[i][i] = w[i], s[i][i] = i;
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= n - i; ++j) {
            l = j, r = i + j;
            for(register int k = l; k <= r; ++k) {
                if(!dp[l][k - 1]) dp[l][k - 1] = 1;
                if(!dp[k + 1][r]) dp[k + 1][r] = 1;
                if(dp[l][r] < dp[l][k - 1] * dp[k + 1][r] + w[k])
                dp[l][r] = dp[l][k - 1] * dp[k + 1][r] + w[k], s[l][r] = k;
            }
        }
    printf("%d\n", dp[1][n]);
    dfs(1, n);
    return 0;
}

Rockdu's Blog