2013-01-24 18:40:16Morris
[ZJ][DP] d841. NOIP2003 3.加分二叉树
內容 ：
设一个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个用空格隔开的整数，为该树的前序遍历。
範例輸入 ：
5 5 7 1 2 10
範例輸出 ：
145 3 1 2 4 5
提示
：
出處
：
/**********************************************************************************/
/* Problem: d841 "NOIP2003 3.加分二叉树" from NOIP2003提高组第三题 */
/* Language: CPP (1355 Bytes) */
/* Result: AC(0ms, 268KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-01-24 17:21:42 */
/**********************************************************************************/
#include <stdio.h>
#include <algorithm>
using namespace std;
long long dp[31][31];
long long A[31];
int used[31][31];
long long dfs(int l, int r) {
if(l > r) return 0;
if(used[l][r]) return dp[l][r];
int i;
long long mx = 0;
for(i = l; i <= r; i++) {
if(l <= i-1 && i+1 <= r)
mx = max(mx, dfs(l, i-1)*dfs(i+1, r)+A[i]);
else if(l <= i-1)
mx = max(mx, dfs(l, i-1)+A[i]);
else if(i+1 <= r)
mx = max(mx, dfs(i+1, r)+A[i]);
else
mx = max(mx, A[i]);
}
used[l][r] = 1;
dp[l][r] = mx;
return mx;
}
void print(int l, int r) {
if(l > r) return;
int i;
long long mx = dp[l][r], tmp;
for(i = l; i <= r; i++) {
if(l <= i-1 && i+1 <= r)
tmp = dfs(l, i-1)*dfs(i+1, r)+A[i];
else if(l <= i-1)
tmp = dfs(l, i-1)+A[i];
else if(i+1 <= r)
tmp = dfs(i+1, r)+A[i];
else
tmp = A[i];
if(mx == tmp) {
printf("%d ", i+1);
print(l, i-1);
print(i+1, r);
return;
}
}
}
int main() {
int n, i;
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%lld", &A[i]);
printf("%lld\n", dfs(0, n-1));
print(0, n-1);
return 0;
}