题目描述
设一个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的前序遍历
————————by洛谷oj
http://www.luogu.org/problem/show?pid=1040
显然一道树形DP 但与主流树形DP不同的是，本题的具体的树不是条件，而是所求。但好在题中还是给了树的中序遍历的（不然怎么做），于是想到中序遍历的性质，点A的左子树在A左，右子树在A右，再分析题意，显然对于每一个根节点A，她的树的加分在确定了左右儿子和儿子子树的最优加分后即可确定，后者由DP实现，前者则需要分别在两个备选点区间中枚举于是得出状态转移方程
f[fa][l][r]=a[fa]+max(f[i][l][fa-1]*f[j][fa+1][r])（i,j）∈{(a,b)|a∈[l,fa-1]，b∈[fa+1,r]}
剩下的就是一些个别的处理了，如当fa-1=l或fa+1=r时特别处理下，之类的。
于是本题的第一个任务完成了，剩下建棵树。这也很简单——对于ls[fa][l][r]和rs[fa][l][r]，f[fa][l][r]转移自i,j，故ls[fa][l][r]=i,rs[fa][l][r]=j;在DP的同时进行。
代码如下：
#include<cstdio>
using namespace std;
int n;
int a[];
long long f[][][];
int ls[][][],rs[][][]; long long dp(int,int,int);
void dlr(int,int,int);
int main()
{
int i,fa;
long long num=,ans=;
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d",&a[i]);
for(i=;i<=n;i++)
{
num=dp(,n,i);
if(ans<num)
{
ans=num;
fa=i;
}
}
printf("%lld\n",ans);
dlr(,n,fa);
}
long long dp(int l,int r,int fa)
{
int i,j;
long long ans;
if(f[fa][l][r]!=)
return f[fa][l][r];
f[fa][l][r]=a[fa];
for(i=l;i<fa;i++)
{
for(j=fa+;j<=r;j++)
{
ans=a[fa]+dp(l,fa-,i)*dp(fa+,r,j);
if(f[fa][l][r]<ans)
{
f[fa][l][r]=ans;
ls[fa][l][r]=i;
rs[fa][l][r]=j;
}
}
}
if(l==fa)
{
for(j=fa+;j<=r;j++)
{
ans=a[fa]+dp(fa+,r,j);
if(f[fa][l][r]<ans)
{
f[fa][l][r]=ans;
rs[fa][l][r]=j;
}
}
}
if(r==fa)
{
for(i=l;i<fa;i++)
{
ans=a[fa]+dp(l,fa-,i);
if(f[fa][l][r]<ans)
{
f[fa][l][r]=ans;
ls[fa][l][r]=i;
}
}
}
return f[fa][l][r];
}
void dlr(int l,int r,int fa)
{
printf("%d ",fa);
if(ls[fa][l][r])
dlr(l,fa-,ls[fa][l][r]);
if(rs[fa][l][r])
dlr(fa+,r,rs[fa][l][r]);
}
当然，本题也可写成区间DP;
最后：
祝AC哟；