5
5 7 1 2 10
145
3 1 2 4 5
我们老师把这道题放到了树形dp里，然而我用树形dp套路肝了两个多小时都没搞出来，然而有一个同学说这是区间dp，
我才恍然大悟，然后用不到1h就写完AC了
1.tree的最高加分：中序遍历有个特点就是假设节点x为根，则对于一个节点y，如果y>x则y在x的右子树上，如果x>y则
y在x的左子树上，这样我们对于每个序列都能很轻松地找到它的最优的根与这最优的值，最后输出最优的值即可
2.tree的前序遍历：这个比起第一个就简单多了，直接一个递归找子节点就好了
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n;
int v[31];
int dp[31][31];
int root[31][31];
int dfs(int l,int r)
{
if(dp[l][r]!=-1)
{
return dp[l][r];
}
if(l==r)
{
return v[l];
}
if(r<l)
{
return 1;
}
for(int i=l;i<=r;i++)
{
int p=dfs(l,i-1)*dfs(i+1,r)+dp[i][i];
if(p>dp[l][r])
{
dp[l][r]=p;
root[l][r]=i;
}
}
return dp[l][r];
}
void print(int l,int r)
{
if(r<l)
{
return;
}
if(l==r)
{
printf("%d ",l);
return;
}
printf("%d ",root[l][r]);
print(l,root[l][r]-1);
print(root[l][r]+1,r);
}
int main()
{
memset(dp,-1,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
dp[i][i]=v[i];
}
printf("%d\n",dfs(1,n));
print(1,n);
return 0;
}
原文：https://www.cnblogs.com/chen-1/p/11326247.html