479. 加分二叉树
设一个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，为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（0<分数<100）。
输出格式
第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。
数据范围
n<30
输入样例：
5
5 7 1 2 10
输出样例：
145
3 1 2 4 5
思路：
由于是中序遍历，我们需要找到一棵树的根节点，根节点就在左子树和右子树的中间，所以区间最后一步的划分就是找到根节点：(f[1,n]=f[1,k-1]*f[k+1,n]+f[k])。由于还需要找到输出前序遍历序列，每次DP时把区间的根节点存下来，DFS搜一遍就可以得到了。
#include<bits/stdc++.h>
using namespace std;
const int N=40;
long long w[N],f[N][N],root[N][N];
void dfs(int l,int r){
if(l>r) return ;
int k=root[l][r];
cout<<k<<" ";
dfs(l,k-1);
dfs(k+1,r);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i) cin>>w[i],root[i][i]=i,f[i][i]=w[i];
for(int len=2;len<=n;++len){
for(int l=1;l+len-1<=n;++l){
int r=l+len-1;
for(int k=l;k<=r;++k){
if(max(1ll,f[l][k-1])*max(1ll,f[k+1][r])+w[k]>f[l][r]){
f[l][r]=max(1ll,f[l][k-1])*max(1ll,f[k+1][r])+w[k];
root[l][r]=k;
}
}
}
}
cout<<f[1][n]<<endl;
dfs(1,n);
return 0;
}
284. 金字塔
虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。
经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。
首先，金字塔由若干房间组成，房间之间连有通道。
如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。
并且，每个房间的墙壁都涂有若干种颜色的一种。
探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。
这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。
机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。
最后，机器人会从入口退出金字塔。
显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。
但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。
现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。
因为结果可能会非常大，你只需要输出答案对109 取模之后的值。
输入格式
输入仅一行，包含一个字符串S，长度不超过300，表示机器人得到的颜色序列。
输出格式
输出一个整数表示答案。
输入样例：
ABABABA
输出样例：
5
前序遍历序列的长度一定是奇数（对于每条边遍历一次再加上一开始的根节点(2*(n-1)+1=2*n-1)），一颗树的前序遍历序列([l,r]，str[l]==str[r])是根节点编号，其中的每一棵子树([l_i,r_i])也都有(str[l_i]==str[r_i])是子树的根节点，并且要被根节点的编号包裹即：(str[l_i-1]==str[r_i+1])是根节点编号。
当合并一个区间序列，我们枚举最后一棵子树的序列区间，所以[l,r]的树，其最后一棵子树可以在([l-1,r-1],[l-2,r-1]...[r-1,r-1])，不能取到r因为我们是化零为整最后一棵子树一定不能为空
#include<bits/stdc++.h>
using namespace std;
const int N=310,mod=1e9;
char str[N];
long long f[N][N];
int main(){
scanf("%s",str+1);
int n=strlen(str+1);
for(int i=1;i<=n;++i) f[i][i]=1;
for(int len=3;len<=n;len+=2){
for(int l=1;l+len-1<=n;++l){
int r=l+len-1;
if(str[l]==str[r]){
for(int k=l+1;k<=r-1;k+=2){
if(str[l]==str[k-1]){
if(str[k]==str[r-1])
f[l][r]+=f[l][k-1]*f[k][r-1];
f[l][r]%=mod;
}
}
}
}
}
cout<<f[1][n];
return 0;
}