题目：
洛谷P1040加分二叉树
大意是给一个正整数序列，它是一棵二叉树的中序遍历结果；一棵树的加分定义为左子树加分x右子树加分+根的值，若某个子树为空，则它的加分是1。
要求输出这棵树的最大加分，和前序遍历结果。
样例输入：
5
5 7 1 2 10
输出：
145
3 1 2 4 5
首先得明白题，对于一个中序遍历序列，二叉树的形态有很多种可能，题目要求找出加分最大的那种形态。对于二叉树，最重要的是确定树根，中序序列[1,n]的树根可能有n种，分别是(1,2,3...n)，枚举每一个可能的树根，递归算出左右子树最大加分，最后将加分最大的定为树根。
一、暴力搜索
#include <cstdio>
#define MAXN 30
typedef long long ll;
using namespace std;
rs表示 区间[i,j]当加分最大时，树的根
int n, a[MAXN+1], rs[MAXN][MAXN];
//搜索从l到r这个区间内的最大加分，并确定根节点
ll dfs(int l, int r){
if (r == l - 1){//这是空树
return 1;
} else if (l == r){//叶子
return a[l];
} else if (r == l + 1){//序列只有两个数，由于是中序，根必然是l
rs[l][r] = l;
return a[l] + a[r];
} else {//枚举每一个数，使其成为根节点，
ll max = -1;
for(int root = l; root <= r; root++){
ll ans = dfs(l, root - 1) * dfs(root + 1, r) + a[root];
if (ans > max){
rs[l][r] = root;
max = ans;
}
}
return max;
}
}
void print(int l, int r){//前序遍历输出
if (l > r){//空树，什么都不输出
return;
} else if (l == r){//叶子，直接输出
printf("%d ", l);
return;
}
int root = rs[l][r];
printf("%d ", root);//先输出根
print(l, root - 1);//输出左子树
print(root + 1, r);//输出右子树
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", a + i);
}
ll ans = dfs(1, n);
printf("%lld\n", ans);
print(1, n);
return 0;
}
二、记忆化，暴力搜索有很多重复计算，比如样例5个数的序列，1为根，[2,5]为右子树时，需要计算[3,5];2为根时，也需要计算[3,5]，很慢，加上记忆化就快了，把算过的存起来，下次直接用。
#include <cstdio>
#define MAXN 30
typedef long long ll;
using namespace std;
int n, a[MAXN+1], rs[MAXN][MAXN];
ll f[MAXN][MAXN];//记忆化数组
ll dfs(int l, int r){
if (r == l - 1){
return 1;
} else if (l == r){
return a[l];
}
if (f[l][r]){
return f[l][r];
}
if (r == l + 1){
rs[l][r] = l;
return f[l][r] = a[l] + a[r];
} else {
ll max = -1;
for(int root = l; root <= r; root++){
ll ans = dfs(l, root - 1) * dfs(root + 1, r) + a[root];
if (ans > max){
rs[l][r] = root;
max = ans;
}
}
return f[l][r] = max;
}
}
void print(int l, int r){
if (l > r){
return;
} else if (l == r){
printf("%d ", l);
return;
}
int root = rs[l][r];
printf("%d ", root);
print(l, root - 1);
print(root + 1, r);
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", a + i);
}
ll ans = dfs(1, n);
printf("%lld\n", ans);
print(1, n);
return 0;
}
三、区间dp
记忆化搜索非常好，但此题对于学习区间dp很有帮助，必须要掌握。
根据记忆化搜索方法，状态和转移方程已经浮现出来,f[i][j]表示中序序列从i到j的最大加分，转移方程为：
f[i][j] = max(f[i][k-1] * f[k+1][j] + a[k]), k属于[i,j]
最终结果就是f[1][n]
dp一般自底向上求解，先解决小问题，然后逐步放大，显然f[i][i]是叶子结点，它的加分是已知的，即f[i][i]=a[i]，f[i][i-1]表示空树，加分是1，把求解区间长度逐渐放大不断扩大规模，即枚举区间长度，从1到n，最后算出f[1][n]。
#include <cstdio>
#define MAXN 30
typedef long long ll;
using namespace std;
int n, rs[MAXN+1][MAXN+1];
ll f[MAXN+1][MAXN+1];
void print(int l, int r){
if (l > r){
return;
} else if (l == r){
printf("%d ", l);
return;
}
int root = rs[l][r];
printf("%d ", root);
print(l, root - 1);
print(root + 1, r);
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &f[i][i]);
f[i][i-1] = 1;
rs[i][i] = i;
}
for(int i = 1; i < n; i++){
f[i][i+1] = f[i][i] + f[i+1][i+1];
rs[i][i+1] = i;
}
for(int len = 3; len <= n; len++){
for(int i = 1; ; i++){
if (i + len - 1 > n) break;
//枚举每一个根，根从i到i+len-1
for(int j = 0; j < len; j++){
int r = i + j;
ll v = f[i][r-1] * f[r+1][i+len-1] + f[r][r];
if (f[i][i+len-1] < v){
f[i][i+len-1] = v;
rs[i][i+len-1] = r;
}
}
}
}
printf("%lld\n", f[1][n]);
print(1, n);
return 0;
}
网友评论